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

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.