Structure connectivity and substructure connectivity of k-ary n-cube networks

The k-ary n-cube is one of the most attractive interconnection networks for parallel and distributed computing system. In this paper, we investigate the fault-tolerant capabilities of k-ary n-cubes with respect to the structure connectivity and substructure connectivity. Let H is a connected graph. The structure connectivity of a graph G, denoted by κ(G; H), is the minimum cardinality of a set of connected subgraphs in G, whose deletion disconnects the graph G and every element in the set is isomorphic to H. The substructure connectivity of a graph G, denoted by κs(G; H), is the minimum cardinality of a set of connected subgraphs in G, whose deletion disconnects the graph G and every element in the set is isomorphic to a connected subgraph of H. We show κ(Qnk;H) and κs(Qnk;H) for each H ∈ {K1, K1, 1, K1, 2, K1, 3}.