A Novel Links Fault Tolerant Analysis: g-Good r-Component Edge-Connectivity of Interconnection Networks With Applications to Hypercubes

This is the authors' abstract. We don't add key points for this paper.

The underlying topology of the interconnection network of parallel and distributed systems is usually modelled by a simple connected graphG. In order to quantitatively analyze the reliability and fault tolerance of these networks more accurately, this study introduces a novel topology parameter. Theg-good$(r+1)$-component edge-connectivityλ g,r+1(G)ofG, 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 leastg. When designing and maintaining parallel and distributed systems, the hypercube networkQₙis one of the most attractive interconnection network models. This article offers a unified method to derive an upper bound forg-good$(r+1)$-component edge-connectivityλ g,r+1(Qₙ)ofQₙ. Whenn≥ 4, this upper bound is proved to be tight for1≤ 2ᵍ· r≤ 2n/2orr=2^k₀,0≤ k₀< n/2,0≤ g≤ n-2k₀-1. The conclusions for theg-good-neighbor edge-connectivity ofQₙfrom Xu and the$(r+1)$-component edge-connectivity ofQₙfrom Zhao et al. are contained as corollaries of our main results for$r=1$,0≤ g≤ n-1and1≤ r≤ 2n/2,$g=0$, respectively.