The g-extra diagnosability of the generalized exchanged hypercube

Abstract

Diagnosability of a self-diagnosable interconnection structure specifies the maximum number of faulty vertices such a structure can identify by itself. A variety of diagnosability models have been suggested. It turns out that a diagnosability property of a network structure is closely associated with its relevant connectivity property. Based on this observation, a general diagnosability derivation process has been suggested. The g-extra connectivity of a graph G characterizes the size of a minimum vertex set F such that, when it is removed, every component in the disconnected survival graph, $G-F,$ contains at least g + 1 vertices. In this paper, we discuss the aforementioned general derivation process, derive the g-extra connectivity, and then apply the aforementioned general process to reveal the g-extra diagnosability of the generalized exchanged hypercube.

Keywords:

• Fault tolerance
• diagnosability
• g-extra connectivity
• g-extra diagnosability
• generalized exchanged hypercube

Disclosure statement

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

Notes

1 We notice that, to show that, for $s_0\le s\le t,|F|\le ks-\frac{k(k-1)}{2}+p,$ there exists Y, a connected component of $GEH(s,t)-F,$ such that, for all $i\in [0,2^s+2^t),$ if $C_i-F_i$ is connected, it is a subgraph of Y, we only need to show, for $s\ge s_0,s(s+1)/2+p<2^s.$ For example, when $(s_0,p)=\left(\right(3,1),(4,5),(5,16),(6,42),\dots ).$ In particular, when $p=1,s_0\ge 3.$

2 Since $g\ge 0$ and $s\ge g+1\ge 1,2s(s+1)\ge \frac{1}{2}s\left[2\right(s+1\left)\right]\ge \frac{1}{2}(g+1)\left[2\right(s+1)-g].$