Structure Fault Tolerance of Recursive Interconnection Networks. (30th January 2020) - Sabir, Eminjan; Meng, Jixiang
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 $λ (G;T)$ (resp. $T$ -substructure edge-connectivity $λ ^s(G;T)$ ) of $G$ is the minimum cardinality of a set of edge-disjoint subgraphs $\mathcal{F}=\{T_{1}, T_{2}, …, T_{m}\}$ (resp. $\mathcal{F}=\{T_{1}^{^{′}}, T_{2}^{^{′}}, …, T_{m}^{^{′}}\}$ ) such that $T_{i}$ is isomorphic to $T$ (resp. $T_{i}^{^{′}}$ 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 $λ (G;T)$ and $λ ^{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.