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
Abstract
The underlying topology of the interconnection network of parallel and distributed systems is usually modelled by a simple connected graph <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$G$</tex-math></inline-formula>. In order to quantitatively analyze the reliability and fault tolerance of these networks more accurately, this study introduces a novel topology parameter. The <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$g$</tex-math></inline-formula>-good <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$(r+1)$</tex-math></inline-formula>-component edge-connectivity <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\lambda _{g,r+1}(G)$</tex-math></inline-formula> of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$G$</tex-math></inline-formula>, if any, is the smallest cardinality of faulty link set, whose malfunction yields a disconnected graph with at least <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$r+1$</tex-math></inline-formula> connected components, and with the neighboring edges of any vertex being at least <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$g$</tex-math></inline-formula>. When designing and maintaining parallel and distributed systems, the hypercube network <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$Q_{n}$</tex-math></inline-formula> is one of the most attractive interconnection network models. This article offers a unified method to derive an upper bound for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$g$</tex-math></inline-formula>-good <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$(r+1)$</tex-math></inline-formula>-component edge-connectivity <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\lambda _{g,r+1}(Q_{n})$</tex-math></inline-formula> of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$Q_{n}$</tex-math></inline-formula>. When <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$n\geq 4$</tex-math></inline-formula>, this upper bound is proved to be tight for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$1\leq 2^{g}\cdot r\leq 2^{\lfloor \frac{n}{2}\rfloor }$</tex-math></inline-formula> or <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$r=2^{k_{0}}$</tex-math></inline-formula>, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$0\leq k_{0}< \lfloor \frac{n}{2}\rfloor$</tex-math></inline-formula>, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$0\leq g\leq n-2k_{0}-1$</tex-math></inline-formula>. The conclusions for the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$g$</tex-math></inline-formula>-good-neighbor edge-connectivity of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$Q_{n}$</tex-math></inline-formula> from Xu and the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$(r+1)$</tex-math></inline-formula>-component edge-connectivity of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$Q_{n}$</tex-math></inline-formula> from Zhao et al. are contained as corollaries of our main results for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$r=1$</tex-math></inline-formula>, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$0\leq g\leq n-1$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$1\leq r\leq 2^{\lfloor \frac{n}{2}\rfloor }$</tex-math></inline-formula>, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$g=0$</tex-math></inline-formula>, respectively.