A general approach to deriving diagnosability results of interconnection networks*

Abstract

We generalise an approach to deriving diagnosability results of various interconnection networks in terms of the popular g-good-neighbour and g-extra fault-tolerant models, as well as mainstream diagnostic models such as the PMC and the MM* models. As demonstrative examples, we show how to follow this constructive, and effective, process to derive the g-extra diagnosabilities of the hypercube, the $(n,k)$-star, and the arrangement graph. These results agree with those achieved individually, without duplicating structure independent technical details. Some of them come with a larger applicable range than those already known, and the result for the arrangement graph in terms of the MM* model is new.

Keywords:

• Fault tolerance
• diagnosability
• g-good-neighbour diagnosability
• g-extra diagnosability
• the hypercube graph
• the $(n,k)$-star graph
• the arrangement graph

Disclosure statement

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

Notes

1 The original notion of a good-neighbour edge-cut of order m as coined in [16] is that a set of edges T in a connected graph G is called a good-neighbour edge-cut of order m if G−F is disconnected and every vertex in G−F has degree at least m.

2 This is where the ‘fault-free’ restriction is needed.

3 Since $F_1\ne F_2,$ either $F_1\setminus F_2\ne set$ or $F_2\setminus F_1\ne set.$

4 For a given pair of supposedly indistinguishable pair of distinct M-faulty set, $F_1,F_2,$ If $F_1\setminus F_2=set,$ then $F_1\subset F_2.$

• If both $F_1$ and $F_2$ are g-good-neighbour faulty sets, then when $F_1\subset F_2,$ any vertex, u, in $V\left(G\right)\setminus (F_1\cup F_2)$ must have at least g neighbouring vertices outside $F_2,$ thus such a vertex u has at least $g(\ge 1)$ neighbours in $V\left(G\right)\setminus (F_1\cup F_2),$ i.e. it is not isolated. This would lead to a simpler argument as given in Proposition 3.9.

• If both $F_1$ and $F_2$ are g-extra faulty sets, then when $F_1\subset F_2,$ any component in $V\left(G\right)\setminus (F_1\cup F_2)$ much have at least g + 1 vertices $F_2,$ thus any vertex u in $V\left(G\right)\setminus \left(F_1{\cup }_2\right)$ has at least one neighbour in $V\left(G\right)\setminus (F_1\cup F_2),$ i.e. it is not isolated, either.

Thus, we can assume that $F_1\setminus F_2\ne set.$ Moreover, since $F_1\ne F_2,$ if $F_1\setminus F_2\ne set,$ then $F_2\setminus F_1\ne set.$

5 We comment that it is this line of reasoning that requires $g\le n-3.$ On the other hand, this condition is only sufficient. For example, if we choose a $K_{1,2}$ in $Q_4$ as shown in Figure 4, when $g=2>1=n-3,$ with $u_0=0000,u_1=0010,$ and $u_2=0100,$ we would still have the result that $Q_{n-1}^R-N\left(Y\right)$ is connected, thus, $Q_n-N^c\left(Y\right)$ contains exactly two components. The upper bound of g can be further expanded via alternative constructions [52, Section 3].

6 The construction of such a tight 3-extra cut will be given later.

7 Since $d(u,w)=2,$ and $k\le n-2,$ by Lemma 6.1, u and w share exactly two common neighbours, one of them being v. Hence, u, v and w share no common neighbours, as v cannot be its own neighbour.

8 We comment that $\sum _{i=1}^n|F_i|=(3k-2)(n-k)-3,$ as expected.

9 We notice that, if we require $k\in [3,n-2],$ we would have $n\ge k+1\ge 4,$ and there would have $(n-2)(n-3)=6$ independent edges between. On the other hand, if $k\in [4,n-1],$ then $n\ge k+1=5,$ and there would be $(n-2)(n-3)(n-4)$ independent edges between, which also leads to six. This is why we have to require $k\in [4,n-2].$

10 It is based on this analysis that we set $k\ge 4,$ hence $n\ge 7.$