Structure Fault Tolerance of Recursive Interconnection Networks. (30th January 2020)

• Record Type: Journal Article
• Authors: Sabir, Eminjan; Meng, Jixiang
• Editors: Stewart, Iain
• Is Part Of: Computer journal. Volume 64:Number 1(2021)
• Page Start: 64
• Page End: 75
• Publication Date: 2020-01-30
• Subjects: fault tolerance -- hypercubes -- k-ary n-cubes -- balanced hypercubes -- structure faults; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxz139
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: Motivated by effects caused by structure link faults in networks, we study the following graph theoretical problem. Let $T$ be a connected subgraph of a graph $G$ except for $K_{1}$ . The $T$ -structure edge-connectivity $\lambda (G;T)$ (resp. $T$ -substructure edge-connectivity $\lambda ^s(G;T)$ ) of $G$ is the minimum cardinality of a set of edge-disjoint subgraphs $\mathcal{F}=\{T_{1}, T_{2}, \ldots, T_{m}\}$ (resp. $\mathcal{F}=\{T_{1}^{^{\prime}}, T_{2}^{^{\prime}}, \ldots, T_{m}^{^{\prime}}\}$ ) such that $T_{i}$ is isomorphic to $T$ (resp. $T_{i}^{^{\prime}}$ is a connected subgraph of $T$ ) for every $1 \le i \le m$, and $E(\mathcal{F})$ 's removal leaves the remaining graph disconnected. In this paper, we determine both $\lambda (G;T)$ and $\lambda ^{s}(G;T)$ for $(1)$ the hypercube $Q_{n}$ and $T\in \{K_{1, 1}, K_{1, 2}, K_{1, 3}, P_{4}, Q_{1}, Q_{2}, Q_{3}\}$ ; $(2)$ the $k$ -ary $n$ -cube $Q^{k}_{n}$ $(k\ge 3)$ and $T\in \{K_{1, 1}, K_{1, 2}, K_{1, 3}, Q^{3}_{1}, Q^{4}_{1}\}$ ; $(3)$ the balanced hypercube $BH_{n}$ and $T\in \{K_{1, 1}, K_{1, 2}, BH_{1}\}$ . We also extend some known results.