Reliability and conditional diagnosability of hyper bijective connection networks

Abstract

The g-extra connectivity and diagonalisability are two important metrics to fault-tolerance and robustness of a multiprocessor system whose network structure is modelled by a graph. In this work, we explore the reliability of a newly proposed network called hyper bijective connection networks (HBC, for short), which is an extension of the family of the well-known interconnection networks, such as hypercube and its variants. We prove that 2-extra vertex connectivity and 3-extra vertex connectivity of n-dimensional HBC are 3n + m−6 for $m\ge 3$ and $n\ge 4$ and 4n + m−8 for $m\ge 4$ and $n\ge 4$, respectively. Using its desirable fault-tolerance, we show that the conditional diagonalizabilities of n-dimensional HBC under the PMC model are m + 4n−7 (resp., 4n−5) for $m\ge 4$ and $n\ge 4$ (resp., m = 3 and $n\ge 4$) and its conditional diagonalizability under MM${}^{\ast }$ model is m + 3n−6 for $m\ge 3$ and $n\ge 4$.

Keywords:

• Hyper bijective connection network
• 2-extra connectivity
• 3-extra connectivity
• Conditional diagonsability
• PMC model
• MM${}^{\ast }$ model

2010 Mathematics Subject Classifications:

• 94C12
• 68M07
• 68M15
• 05C40

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was supported by National Natural Science Foundation of China [61977016, 61572010] and National Natural Science Foundation of Fujian Province [2017J01738].