Structure connectivity and substructure connectivity of n$-cube networks

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 the structure/substructure connectivity of $Q{n}{k}$ networks, for paths and cycles, 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). Lv et 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})$.