TY - JOUR

T1 - Structure connectivity and substructure connectivity of n$-cube networks

AU - Zhang, Guozhen

AU - Wang, Dajin

N1 - Publisher Copyright:
© 2013 IEEE.

PY - 2019

Y1 - 2019

N2 - 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})$.

AB - 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})$.

KW - Cycless

KW - Interconnection networks

KW - K-ary n-cubes

KW - Paths

KW - Structure connectivity

KW - Substructure connectivity

UR - http://www.scopus.com/inward/record.url?scp=85078280007&partnerID=8YFLogxK

U2 - 10.1109/ACCESS.2019.2941711

DO - 10.1109/ACCESS.2019.2941711

M3 - Article

AN - SCOPUS:85078280007

SN - 2169-3536

VL - 7

SP - 134496

EP - 134504

JO - IEEE Access

JF - IEEE Access

M1 - 8839769

ER -