Structure Connectivity and Substructure Connectivity of $k$ -Ary $n$ -Cube Networks
Guozhen Zhang, Dajin Wang · IEEE Access · 2019
We present new results on the fault tolerability of$k$-ary$n$-cube (denoted$Q_{n}^{k}$) networks.$Q_{n}^{k}$is a topological model for interconnection networks that has been extensively studied since proposed, and this paper is concerned with thestructure/substructure connectivityof$Q_{n}^{k}$networks, forpathsandcycles, two basic yet important network structures. Let$G$be a connected graph and$T$a connected subgraph of$G$. The$T$-structure connectivity$\kappa (G; T)$of$G$is the cardinality of a minimum set of subgraphs in$G$, such that each subgraph is isomorphic to$T$, and the set’s removal disconnects$G$. The$T$-substructure connectivity$\kappa ^{s}(G; T)$of$G$is the cardinality of a minimum set of subgraphs in$G$, such that each subgraph is isomorphic to a connected subgraph of$T$, and the set’s removal disconnects$G$. In this paper, we study$\kappa (Q_{n}^{k}; T)$and$\kappa ^{s}(Q_{n}^{k}; T)$for$T=P_{i}$, a path on$i$nodes (resp.$T=C_{i}$, a cycle on$i$nodes). Lvet al.determined$\kappa (Q_{n}^{k}; T)$and$\kappa ^{s}(Q_{n}^{k}; T)$for$T\in \{P_{1},P_{2},P_{3}\}$. Our results generalize the preceding results by determining$\kappa (Q_{n}^{k}; P_{i})$and$\kappa ^{s}(Q_{n}^{k}; P_{i})$. In addition, we have also established$\kappa (Q_{n}^{k}; C_{i})$and$\kappa ^{s}(Q_{n}^{k}; C_{i})$.