A Novel Links Fault Tolerant Analysis: $g$-Good $r$-Component Edge-Connectivity of Interconnection Networks With Applications to Hypercubes
Hongxi Liu, Mingzu Zhang, Sun‐Yuan Hsieh, Chia‐Wei Lee · IEEE Transactions on Reliability · 2024
The underlying topology of the interconnection network of parallel and distributed systems is usually modelled by a simple connected graph$G$. In order to quantitatively analyze the reliability and fault tolerance of these networks more accurately, this study introduces a novel topology parameter. The$g$-good$(r+1)$-component edge-connectivity$\lambda _{g,r+1}(G)$of$G$, if any, is the smallest cardinality of faulty link set, whose malfunction yields a disconnected graph with at least$r+1$connected components, and with the neighboring edges of any vertex being at least$g$. When designing and maintaining parallel and distributed systems, the hypercube network$Q_{n}$is one of the most attractive interconnection network models. This article offers a unified method to derive an upper bound for$g$-good$(r+1)$-component edge-connectivity$\lambda _{g,r+1}(Q_{n})$of$Q_{n}$. When$n\geq 4$, this upper bound is proved to be tight for$1\leq 2^{g}\cdot r\leq 2^{\lfloor \frac{n}{2}\rfloor }$or$r=2^{k_{0}}$,$0\leq k_{0}< \lfloor \frac{n}{2}\rfloor$,$0\leq g\leq n-2k_{0}-1$. The conclusions for the$g$-good-neighbor edge-connectivity of$Q_{n}$from Xu and the$(r+1)$-component edge-connectivity of$Q_{n}$from Zhao et al. are contained as corollaries of our main results for$r=1$,$0\leq g\leq n-1$and$1\leq r\leq 2^{\lfloor \frac{n}{2}\rfloor }$,$g=0$, respectively.