# On Fault Identification in Interconnection Networks under the Comparison Model

Authors: Jiarong Liang; Qian Zhang
Journal: Discrete Dynamics in Nature and Society
 (2018)

---

## Abstract

We propose three characterization theorems oft/t-diagnosable systems under the comparison model. By these characterization theorems we present some properties of t/t-diagnosable systems. Furthermore, for a given network system, we introduce a new method to determine a range from tmin to tmax conveniently, in which the system is at least tmin/tmin-diagnosable and at most tmax/tmax-diagnosable. By applying our results to some well-known networks such as n-dimensional hypercube, 2D (3D) mesh, and permutation star graph, we figure out their t/t-diagnosability.


---

## Body

## 1. Introduction

With the rapid development of digital technology, multiprocessor computer systems can now contain hundreds and thousands of processors. It is inevitable that some processors in such a system may fail. To ensure reliability, the system should have the ability to identify the faulty processors which can be isolated from the system or replaced by additional fault-free ones. In large multiprocessor computer systems, it is difficult and impractical for each processor to be tested individually by another host. So, it is important and significant to design an effective method of fault diagnosis for such systems in the situation. System-level diagnosis, which is first proposed by Preparata et al. in [1, 2], is an important self-diagnosis strategy. In [1], Preparata et al. introduced the first system-level diagnosis model, called the PMC model, which can be represented by a digraph G=(V,E) and the edge (i,j) means node i tests node j. The test outcome of node i testing node j is represented by ω(i,j). ω(i,j)=1(0) implies that node i judges node j to be faulty (fault-free) and the outcome of test (i,j) is reliable only if node i is fault-free. The PMC model has widely been adopted (see [3–8]). Another practical model is the comparison model (also called MM model), proposed by Maeng and Malek [9, 10]. Sengupta and Dahbura [11] suggested a further modification, called the MM∗ model, in which any node has to test another two nodes if it is adjacent to them. A comparison model can be represented by an undirected graph G=(V,E). Under the comparison model, node k is a comparator for nodes i and j if and only if (i,k)∈E and (j,k)∈E. The test outcome of comparator k testing i,j is denoted by ω(k:i,j). ω(k:i,j)=1 implies that at least one of the nodes i, j, and k is faulty and ω(k:i,j)=0 implies that if node k is fault-free, then nodes i and j are all fault-free. The test outcome ω(k:i,j) is reliable only if node k is fault-free. In other words, if node k is faulty, then ω(k:i,j) can be arbitrary. It is worth noting that PMC model is a special case of the comparison model [11]. The MM model and the MM∗ model were adopted in [11–16].There are two fundamentally different strategies to system-level diagnosis:t-diagnosable [1] and t/t-diagnosable [17]. A system is t-diagnosable if and only if all faulty nodes can be correctly identified in the presence of at most t faulty nodes in this system. And a system is t/t-diagnosable if and only if all faulty nodes can be isolated within a set of sizes at most t in the presence of at most t faulty nodes. Under the PMC model, Hakimi and Amim [18] characterized t-diagnosable systems and [19, 20] characterized t/t-diagnosable systems. Under the comparison model, Sengupta and Dahbura [11] proposed a characterization of t-diagnosable systems. However, the t/t-diagnosable systems have not been as yet characterized under the comparison model. Furthermore, comparing to PMC model, comparison model has a better stability and reliability. And comparing to t-diagnosable systems, t/t-diagnosable systems have an almost 50 percent reduction in the number of the tests. This provides a strong motivation for the study of t/t-diagnosable systems under the comparison model.In the next section we shall present a characterization oft/t-diagnosable systems under the comparison model. In Section 3 we shall propose some practical properties of AFS’s in t/t-diagnosable systems. And in Section 4 we shall use the characterization of t/t-diagnosable systems to figure out the t/t-diagnosability of some special interconnection networks such as n-dimensional hypercube, 2D (3D) mesh, and permutation star graph. In Section 5, simulations and comparisons of the t-diagnosability and the t/t-diagnosability for the interconnection networks are presented. In the last section we draw a conclusion.


## 2. Characterization oft/t-Diagnosable Systems

Before we present the characterization oft/t-diagnosable systems, we shall do some preliminaries as follows.Definition 1 (see [11]).
Given a systemG=(V,E) and a syndrome σ, a set X⊂V is called an allowable fault set (AFS) of the system for σ if, for any three nodes i,j,k∈V such that (i,k)∈E, (j,k)∈E,
(i) ifk∈V-X and i,j∈V-X then ω(k:i,j)=0,
(ii) ifk∈V-X and {i,j}∩X≠ϕ then ω(k:i,j)=1.For a systemG=(V,E) and a syndrome σ, let(1)Ωσ,t=F:FisanAFSofσ,F⩽t.Lemma 2.
Given a systemG=(V,E) and a syndrome σ, with S1,S2 where S1,S2⊂V are two allowable fault sets for the syndrome σ, (S1∪S2) is also an allowable fault set.Proof.
LetS0=(S1∪S2) and assume, to the contrary, that S0 is not an allowable set. Then, for S0, there exist three nodes i,j,k∈V such that (i,k)∈E, (j,k)∈E, and at least one of the conditions of Definition 1 cannot be satisfied.
If condition(i) cannot be satisfied, then there exist three nodes i,j,k∈V-S0 such that ω(k:i,j)=1; thus, S1,S2 are not allowable fault sets, a contradiction.
Similarly, if condition(ii) cannot be satisfied, then there exists a node k∈V-S0 and two nodes i,j,{i,j}∩S0≠ϕ such that ω(k:i,j)=0. It is obvious that if above condition is satisfied, then at least one of S1,S2 is not an allowable fault set, which is also a contradiction to the hypothesis.For a system given byG=(V,E) and for a set of nodes X⊂V, T(X) denotes the set of those nodes in V-X which are compared to some node of X by some node of X: T(X)={j|(i,k)∈E,(j,k)∈E and i,k∈X}-X. For a set of nodes X⊂V, GX=(VX,EX) denotes a graph defined on the set of nodes in V-X-T(X), where VX=V-X-T(X) and EX={(i,j)|i,j∈VXand∃k∈X such that (i,k)∈E,(j,k)∈E}.As an example, for the system of Figure1, if X={4,5,6}, then T(X)={1,7} and VX={2,3}, EX={(2,3)}.Figure 1
An interconnection topology graphG with 7 nodes.Definition 3.
A graph denoted byG=(V,E) is a bipartite graph if there exist two sets P,Q such that P∩Q=ϕ, P∪Q=V and for each edge (i,j)∈E, i and j are, respectively, in the two sets(P and Q).With above preliminaries, we shall state the following theorem. In the following theorem, we useLα,β to denote the set of bipartite graphs with α and β nodes in the two sets of the bipartition.Theorem 4.
A system withn nodes given by G=(V,E) is t/t-diagnosable if and only if (i)n⩾2t+1 and (ii) for each X⊂V such that |X|=n-2t+p, 0⩽p⩽t-1, GX does not have Lα,β with α+β=2(t-p) as a node induced subgraph.Proof.
Necessity. It is obvious that condition (i) must be satisfied; thus we consider condition (ii) now. Suppose that for some X⊂V such that |X|=n-2t+p, 0⩽p⩽t-1, GX=(VX,EX) has Lα,β with α+β=2(t-p) as a node induced subgraph. Then we have that |V-X|=2t-p, |VX|⩾2(t-p), and |T(X)|=|V-X-VX|⩽p. Let {P,Q} be the bipartition of Lα,β such that |P|=α,|Q|=β. Let Y=V-X-P-Q-T(X); then |Y|=p-|T(X)|. Let S1=P∪T(X)∪Y, S2=Q∪T(X)∪Y, then we have that |S1|=p+α,|S2|=p+β and V-S1-S2=X, S1-S2=P, S2-S1=Q. For the sake of convenience, we make the Venn diagram of the graph G (shown by Figure 2). Note that P⊂V-X-T(X); it is easily obtained that for each pair {j,k}⊂X with (j,k)∈E there exists no edge from P to {j,k}. Similarly there exists no edge from Q to {j,k}. On the other hand, since P and Q are the bipartition of Lα,β, which is a node induced graph of GX, any two nodes in P(or Q) are nonadjacent in GX. Hence, no two nodes of P(or Q) are compared by some node of X.
Consider a syndromeσ such that for nodes i,j,k∈V with (i,k)∈E and (j,k)∈E
(i) ifi,j,k∈X, then ω(k:i,j)=0;
(ii) ifi∈S1∪S2, j,k∈X, then ω(k:i,j)=1;
(iii) ifi,j∈S1∪S2 and k∈X, then ω(k:i,j)=1;
(iv) ifi,k∈S1∪S2 and j∈X, then if i,k∈S1-S2 or i,k∈S2-S1, then ω(k:i,j)=0; otherwise ω(k:i,j)=1;
(v) ifi,j,k∈S1∪S2,then if i,j,k∈S1-S2 or i,j,k∈S2-S1, then ω(k:i,j)=0; otherwise ω(k:i,j)=1;
(vi) ifk∈(S1-S2)∪(S2-S1) and i,j∈X, then ω(k:i,j)=0;
(vii) the other possible test results are arbitrary.
According to Definition1, it can be easily seen that S1 and S2 are allowable fault sets for σ. But S1∪S2=2t-p>t, which is a contraction to the assumption that the system is t/t-diagnosable.
Sufficiency. Suppose that the system is not t/t-diagnosable. Then for some syndrome σ, we have r⩾2 distinct allowable fault sets Vf1,Vf2,⋯,Vfr⊆V with |Vfi|⩽t such that ∪i=1rVfi>t. Let k∈{1,2,⋯,r} be the minimum integer such that ∪i=1k-1Vfi⩽t and ∪i=1kVfi=2t-p>t(0⩽p<t). Let F1=∪i=1k-1Vfi and F2=Vfk. By Lemma 2, we can easily get that F1 is an allowable fault set. Let Vc=F1∩F2, V′=∪i=1kVfi-Vc=(F1-F2)∪(F2-F1). By definition of the k, we can easily see that |Vc|⩽p. Let X=V-∪i=1kVfi=V-(F1∪F2); then |X|=n-2t+p and T(X)⊆Vc. Since both of F1 and F2 are allowable fault sets, (F1-F2)∪(F2-F1)⊆VX and |(F1-F2)∪(F2-F1)|⩾2t-p-Vc⩾2(t-p). Note that there always exist two sets P and Q such that P is a subset of (F1-F2) and Q is a subset of (F2-F1) with |P|+|Q|=2(t-p). Thus, for any two nodes in P(or Q), they are nonadjacent in GX. It is obvious that {P,Q} are the two parts of the bipartite graph of GX with |P|+|Q|=2(t-p), a contradiction. This completes the proof.Figure 2
The Venn diagram of graph G.Although Theorem4 gives the characterizations to judge whether a system is t/t-diagnosable or not, it is abstract. Next, we shall present an alternative characterization of t/t-diagnosable systems.Lemma 5 (see [11]).
For anyS1,S2⊂V with S1≠S2, (S1,S2) is a distinguishable pair if and only if at least one of the following conditions is satisfied:
(1)∃i,k∈V-S1-S2 and ∃j∈(S1-S2)∪(S2-S1) such that (i,k)∈E and (j,k)∈E,
(2)∃i,j∈S2-S1 and ∃k∈V-S1-S2 such that (i,k)∈E and (j,k)∈E, or
(3)∃i,j∈S1-S2 and ∃k∈V-S1-S2 such that (i,k)∈E and (j,k)∈E.It is easily seen that ifS1,S2 are all allowable fault sets for a syndrome σ, then (S1,S2) is an indistinguishable pair.Theorem 6.
LetG=(V,E) be the undirected graph of a system S with n nodes and n⩾2t+1. Then the following statements are equivalent.
(i)S is t/t-diagnosable.
(ii) For any two sets of nodesS1,S2⊆V with |S1|=|S2|=t and S1≠S2, at least one of the conditions of Lemma 5 is satisfied.
(iii) For any two sets of nodesS1,S2⊆V with |S1|,|S2|⩽t and S1⊈S2 and S2⊈S1, at least one of the conditions of Lemma 5 is satisfied.Proof.
( i ) ⇒ ( i i ). Suppose that the system is t/t-diagnosable and, to the contrary, there are two sets of nodes S1,S2⊆V with |S1|=|S2|=t and S1≠S2, such that none of the conditions of Lemma 5 can be satisfied. Let X=V-S1-S2; consider a syndrome σ such that, for nodes i,j,k∈V with (i,k)∈E and (j,k)∈E,
(1) ifi,j,k∈X, then ω(k:i,j)=0;
(2) ifi∈S1∪S2, j,k∈X, then ω(k:i,j)=1;
(3) ifi,j∈S1∪S2 and k∈X, then ω(k:i,j)=1;
(4) ifi,k∈S1∪S2 and j∈X, then if i,k∈S1-S2 or i,k∈S2-S1, then ω(k:i,j)=0; otherwise ω(k:i,j)=1;
(5) ifi,j,k∈S1∪S2, then if i,j,k∈S1-S2 or i,j,k∈S2-S1, then ω(k:i,j)=0; otherwise ω(k:i,j)=1;
(6) the other possible test results are arbitrary.
It can observed thatS1,S2 are all allowable fault sets for above syndrome σ. Since S1∪S2>t, the system is not t/t-diagnosable, which is a contradiction.
( i i ) ⇒ ( i i i ). Consider any two sets of nodes S1,S2⊆V with |S1|,|S2|⩽t and S1⊈S2 and S2⊈S1. Without loss of generality, we can assume |S1|⩽|S2|. Choose a set of nodes Sx⊆(S2-S1) such that |Sx|+|S1|=|S2|. Choose a set of nodes Sy⊆(V-S2-S1) such that |Sy|+|S2|=t. Let U1=S1∪Sx∪Sy and U2=S2∪Sy. Clearly, |U1|=|U2|=t and note that
(1)S1-S2=U1-U2,
(2)S2-S1⊇U2-U1,
(3)V-S2-S1⊇V-U2-U1.
According to the hypothesis, we have that forU1 and U2 at least one of the conditions of Lemma 5 are satisfied. Therefore, by (1), (2), and (3), for S1 and S2 at least one of the conditions of Lemma 5 is also satisfied.
( i i i ) ⇒ ( i ). Assume, to the contrary, the system is not t/t-diagnosable. Then for some syndrome σ, we have r⩾2 distinct allowable fault sets Vf1,Vf2,…,Vfr⊆V with Vfi⩽t such that ∪i=1rVfi>t. Let k∈{1,2,⋯,r} be the minimum integer such that ∪i=1k-1Vfi⩽t and ∪i=1kVfi=2t-p>t(0⩽p<t). Let F1=∪i=1k-1Vfi and F2=Vfk. By Lemma 2, we can easily see that F1 is an allowable fault set for σ; thus, (F1,F2) is an indistinguishable pair. Since |F1|,|F2|⩽t and F1⊈F2 and F2⊈F1, for F1,F2 at least one of the conditions of Lemma 5 is satisfied. So, (F1,F2) is a distinguishable pair. This is a contradiction.From the definition of the allowable fault set, we conclude that all faulty nodes must be isolated in union set of all allowable fault sets. In next section, we shall propose some practical properties oft/t-diagnosable system.


## 3. Properties oft/t-Diagnosable Systems

Theorem 7.
For at/t-diagnosable system G=(V,E) and a syndrome σ in most t faulty nodes situation, if Fi,Fj∈Ωσ,t, then Fi⊆Fj or Fj⊆Fi.Proof.
Suppose that, to the contrary, there exist two sets of nodesFi,Fj∈Ωσ,t such that Fi⊈Fj and Fj⊈Fi, which implies that (Fi,Fj) is an indistinguishable pair. On the other hand, by Theorem 6, for Fi,Fj at least one of the conditions of Lemma 5 is satisfied; thus, (Fi,Fj) is a distinguishable pair. This is a contradiction.Theorem 8.
For at/t-diagnosable system G=(V,E) and a syndrome σ in most t faulty nodes situation, if Fi,Fj∈Ωσ,t, then |Fj-Fi|⩽1.Proof.
Suppose that, to the contrary, there exist two sets of nodesFi,Fj∈Ωσ,t such that such that |Fj-Fi|⩾2. It follows from Theorem 6 that Fj⊃Fi and |Fj|-|Fi|=|Fj-Fi|⩾2. Let |Fj|-|Fi|=|Fj-Fi|=2q+r, where q⩾1 is an integer and r=0 or 1. So, |Fj|=|Fi|-2q-r⩽t-2q-r. Let Fj′⊆(Fj-Fi) be the subset of Fj-Fi such that |Fj′|=2q=2(t-p), where ⌊t/2⌋-1⩽p⩽t-1. Let R be the subset of V-Fj such that |Fj|+|R|=2t-p. Let Ssub=Fj-Fi-Fj′. Partition Fj′ into two parts P and Q such that |Q|=|P|=t-p. Let S1=P∪Ssub∪Fi∪R and S2=Q∪Ssub∪Fi∪R. Note that |S1|=|S2|=2t-p-(t-p)=t, S1-S2=P, and S2-S1=Q. Since S1≠S2, for S1 and S2, at least one of the conditions of Lemma 5 is satisfied. It is easily seen that, for S1 and S2, if any one condition of Lemma 5 is satisfied, then Fj and Fi cannot be AFS at the same time, a contradiction.Theorem 9.
IfS is a t/t-diagnosable system with f faulty nodes (1⩽f⩽t), given any syndrome σ, then each of the following conditions must hold:
(i)1⩽|Ωσ,t|⩽2.
(ii) IfΩσ,t={Fi,Fj} where Fi≠Fi, then either Fi⊂Fj with Fj-Fi=1 or Fj⊂Fi with Fi-Fj=1.Proof.
Since the set of all faulty nodes is ASF, we have that1⩽|Ωσ,t|. Subsequently, we will prove |Ωσ,t|⩽2. Assume, to the contrary, that |Ωσ,t|⩾3. Then, by Theorem 7, there exist at least three distinct AFS F1,F2,F3∈Ωσ,t such that F1⊂F2⊂F3. Therefore, |F3-F1|⩾2, which is a contradiction to Theorem 8.
Theorems7 and 8 imply that condition (ii) is true.With the above characterizations and properties of thet/t-diagnosable system, we are able to judge whether an interconnection network is a t/t-diagnosable system or not. In next section, for some practical interconnection networks such as n-dimensional hypercube, 2D (3D) mesh, and permutation star graph, we shall find out a maximum value of t such that these interconnection networks are t/t-diagnosable systems.


## 4. Application

In fact, for a given value oft, using Theorems 4 and 6 to verify whether a system is t/t-diagnosable or not is very complicated. Now, we will propose a simple sufficient condition and a simple necessary condition to test whether a system is t/t-diagnosable.A system is given byG=(V,E). For a node i∈V, let N(i)={j|(i,j)∈Eandj≠i}; for a set of nodes X⊂V, let N(X)=∪i∈XN(i)-X.Theorem 10.
Let G=(V,E) be the undirected graph of a systemS. If S is a t/t-diagnosable system, then |N({i,j})|⩾t for each pair of nodes {i,j}⊂V.Proof.
Assume that the system ist/t-diagnosable and there is one pair of nodes {i,j} such that Ni,j<t. Let S1=N({i,j})∪{i} and S2=N({i,j})∪{j}. Note that |S1|⩽t, |S2|⩽t and S1-S2={i}, S2-S1={j}. Then for S1, S2, none of the conditions of Lemma 5 is satisfied, which is a contradiction to Theorem 6.Theorem 11.
LetG=(V,E) be the undirected graph of a system S. If |N({i,j})|⩾2t-1(t⩾3) for each pair of nodes {i,j}⊂V and |N(i)|⩾t+1 for each node i∈V, then S is a t/t-diagnosable system.Proof.
Assume that the system is nott/t-diagnosable. By Theorem 6, there exist two sets S1,S2⊆V with |S1|=|S2|=t and S1≠S2 such that none of the conditions of Lemma 5 is satisfied. Let |S1-S2|=|S2-S1|=p,1⩽p⩽t. Consider the following cases.
Case 1 (p=1). Let {i}=S1-S2, {j}=S2-S1. Since |N({i,j})|⩾2t-1 and |S1∩S2|=t-1, note that when t⩾3, |N({i,j})|-|S1∩S2|⩾2t-1-(t-1)=t⩾3, there exist at least two nodes k,l∈V-S1-S2 such that (i,k)∈E and (i,l)∈E or (j,k)∈E and (j,l)∈E. Without loss of generality, let (i,k)∈E and (i,l)∈E. Since |N({k,l})|⩾2t-1 and |S1∪S2|=t+1, note that when t⩾3, |N({k,l})|-|S1∪S2|⩾2t-1-(t+1)=t-2⩾1, there exists a node m∈V-S1-S2 such that (m,k)∈E or (m,l)∈E. Then for the three nodes m,k,i or m,j,i, condition (1) of Lemma 5 is satisfied, a contradiction.
Case 2 (p⩾2). Let {i,j}⊆S1-S2. Since |N({i,j})|⩾2t-1 and |S1∪S2-{i,j}|⩽2t-2, there exists a node k∈V-S1-S2 such that (i,k)∈E or (j,k)∈E. Without loss of generality, let (i,k)∈E. Since |N({i,k})|⩾2t-1 and |N(k)|⩾t+1, there must exist a node l∈V-S2 such that (l,k)∈E. Then for i,k,l, at least one condition of Lemma 5 (condition (1) or (2)) is satisfied, a contradiction.Note that, for a given system, by using Theorems10 and 11, we are able to obtain a range from tmin to tmax conveniently, in which the system is at least tmin/tmin-diagnosable and at most tmax/tmax-diagnosable. In other words, for a system S, let G=(V,E) denote its diagnostic graph, m=min{Ni,ji,j∈V},M=max{Ni,ji,j∈V}; then we conclude that S is at least m/m-diagnosable and is at most M/M-diagnosable.


### 4.1.n-Dimensional Hypercube

Ann-dimensional hypercube Qn has 2n nodes and each node is labeled by an n-bit binary string. Two nodes are adjacent if and only if their labels differ in exactly one bit position [21]. Since for each adjacent pair of nodes {i,j}⊂Qn, Ni,j=2n-2<2n-1, by Theorem 10 we have that the n-dimensional hypercube is not (2n-1)/(2n-1)-diagnosable. Next, we shall show that an n-dimensional hypercube is (2n-2)/(2n-2)-diagnosable.Lemma 12 (see [22]).
LetG=(V,E) be the graph of a hypercube of n dimension and X⊂V with |X|=k, 0<k⩽n+1, then N(X)⩾kn-k(k+1)/2+1.Theorem 13.
Ann-dimensional(n⩾6) hypercube Qn, denoted by G=(V,E), is a (2n-2)/(2n-2)-diagnosable system.Proof.
Assume that, to the contrary, ann-dimensional hypercube Qn is not a (2n-2)/(2n-2)-diagnosable system. Then there exist two sets of nodes S1,S2⊆Qn with |S1|=|S2|=2n-2 and S1≠S2, such that none of the three conditions of Lemma 5 is satisfied. Let |S1-S2|=|S2-S1|=p, 1⩽p⩽2n-2. Consider the following cases.
Case 1 (p=1). Let {i}=S1-S2, {j}=S2-S1. Since |N({i,j})|⩾2n-2 and |S1∩S2|=2n-3, there exists a node k∈V-S1-S2 such that (i,k)∈E or (j,k)∈E. Without loss of generality, let (i,k)∈E; then N(k)-{i}⊆S2. Otherwise there exists a node v∈V-S1-S2 such that the three nodes i, j, and k satisfy condition (1) of Lemma 5, a contradiction. We claim that N(i)-{k}⊈S2. Otherwise, note that (N(k)-{i})∩(N(i)-{k})=ϕ and |N(k)-{i}|+|N(i)-{k}|=|S2|=2n-2. Combining the address structure of Qn(n⩾6), we have that there exist two nodes a,b∈V-S1-S2 such that for nodes a,b,j, condition (1) of Lemma 5 is satisfied. Therefore N(i)-{k}⊈S2. Let l∈N(i)-{k} and l∉S2. Let X={i,k,l}; we have |N(X)|⩾3n-5. So, |N(X)|-|S2|⩾3n-5-(2n-2)=n-3⩾3(n⩾6). Without loss of generality, let v∈N(X) and v∉S2. We claim that v∈N(i). Otherwise, for nodes v,i,k(l), condition (1) of Lemma 5 is satisfied. Thus, v∈N(i); then let Y={v,l,k}, according to Lemma 12, we have |N(Y)|⩾3n-5. Let η=|N(X)|-|S1∪S2|⩾3n-5-(2n-1)=n-4. When n⩾6, we have η⩾2. Without loss of generality, let u∈N(Y) and u∉(S1∪S2). Then for nodes u,i,k(lorv), condition (1) of Lemma 5 is satisfied, a contradiction.
Case 2 (p=2). Let {i,j}=S1-S2, {i′,j′}=S2-S1, and X={i,j,i′,j′}. By Lemma 12 we know that N(X)⩾4n-9 and |S1∩S2|=2n-4. |N(X)|-|S1∩S2|⩾4n-9-(2n-4)=2n-5⩾7(n⩾6). Let Y={a,b,c,d} with Y⊂N(X) and Y∩(S1∩S2)=ϕ. According to Lemma 12, we have |N(Y)|⩾4n-9, |N(X)|-|S1∪S2|⩾4n-9-2n=2n-9⩾3(n⩾6). Thus, there exists a node v such that v∈N(Y) and v∉(S1∪S2). Without loss of generality, let (a,i)∈E and (a,v)∈E. Then, for nodes a,v,i, condition (1) of Lemma 5 is satisfied, a contradiction.
Case 3 (3⩽p⩽2n-7). Since |S1-S2|=|S2-S1|=p(3⩽p⩽2n-7), there always exists a set X⊆(S1-S2)∪(S2-S1) with |X|=6 such that N(X)⩾6n-20. Note that |S1∪S2-X|⩾4n-9-6=4n-15 and |N(X)|-|S1∪S2-X|⩾6n-20-(4n-15)=2n-5⩾7(n⩾6). Then there exists a set Y={a,b,c,d,e,f,g} such that Y⊂N(X) and Y∩(S1∪S2)=ϕ. According to Lemma 12, we have N(Y)⩾6n-20. |N(Y)|-|S1∪S2|⩾6n-20-(2n-2+p)⩾4n-18-p⩾4n-18-(2n-7)=2n-11⩾1(n⩾6). Thus, there exists a node v such that v∈N(Y) and v∉(S1∪S2). Without loss of generality, let i∈X, (a,i)∈E, and (a,v)∈E. Then for nodes a,v,i, condition (1) of Lemma 5 is satisfied, a contradiction.
Case 4 (2n-6⩽p⩽2n-2). Since |S1-S2|=|S2-S1|=p, when n⩾6, we have p⩾6. Then there always exists a set X⊆(S1-S2) with |X|=6 such that N(X)⩾6n-20. |N(X)|-|S1∪S2-X|⩾6n-20-(4n-10)=2n-10⩾2(n⩾6). Then there exists a set Y={a,b}⊂N(X) such that Y∩(S1∪S2)=ϕ. According to Lemma 12, we have N(Y)⩾2n-2. |N(Y)|-|S1∩S2|⩾2n-2-4=2n-6⩾6(n⩾6). Thus, there exists a set Z⊂N(Y) with |Z|=3 such that Z⊂S1-S2 or Z⊂S2-S1. Note that Z⊂N(Y), |Z|=3 and Y⊂N(Z), |Y|=2. Thus, there must exist one node in Y connecting two nodes in Z. Without loss of generality, let i,j∈Z, (a,i)∈E, and (a,j)∈E; then, for nodes a,i,j, condition (2) of Lemma 5 is satisfied, a contradiction.
Above all, ann-dimensional (n⩾6) hypercube Qn is a (2n-2)/(2n-2)-diagnosable system.


### 4.2.2D and 3D Mesh

A2D mesh contains n2 nodes and each node is labeled with a two-bit string such as aij(0⩽i⩽n-1,0⩽j⩽n-1). Two nodes aij and ai′j′ are adjacent if and only if one of the following conditions is satisfied.(i)
i+1modn=i′ and j=j′.(ii)
(i-1)modn=i′ and j=j′.(iii)
(j+1)modn=j′ and i=i′.(iv)
(j-1)modn=j′ and i=i′.LetG=(V,E) be the graph of a 2D mesh with n2 nodes and X⊂V with |X|=k, 0<k⩽(n-1)2; let N(X,k) denote the value of |N(X)|.Observe thatN(X,2)⩾6, N(X,3)⩾7, N(X,4)⩾8, N(X,6)⩾9, and N(X,8)⩾11.Lemma 14.
LetG=(V,E) be the graph of a 2D mesh with n2 nodes, X⊂V; if any two nodes of X are not adjacent, then N(X,3)⩾8, N(X,4)⩾9, N(X,6)⩾13.Proof.
Using exhaustive method, we can easily get that the conclusion is true.For each adjacent pair of nodes{i,j}⊂V, we always have Ni,j=6<7, by Theorem 10 we have that the 2D mesh with n2 nodes is not 7/7-diagnosable. Next, we shall show that a 2D mesh with n2 nodes is a 6/6-diagnosable system.Theorem 15.
A2D mesh with n2 nodes (n⩾5), denoted by G=(V,E), is a 6/6-diagnosable system.Proof.
Assume that, to the contrary, a2D mesh with n2 nodes, denoted by G=(V,E), is not a 6/6-diagnosable system. Then there exist two sets of nodes S1,S2⊂V with |S1|=|S2|=6 and S1≠S2, such that for S1 and S2 none of the three conditions of Lemma 5 is satisfied. Let |S1-S2|=|S2-S1|=p, 1⩽p⩽6. Consider the following cases.
Case 1 (p=1). Let {i}=S1-S2, {j}=S2-S1. Since |N({i,j})|⩾6 and |S1∩S2|=5, there exists a node k∈V-S1-S2 such that (i,k)∈E or (j,k)∈E. Without loss of generality, let (i,k)∈E; then we have N(k)-{i}⊆S2. If N(i)-{k}⊆S2, note that (N(k)-{i})∩(N(i)-{k})=ϕ; this implies that |N(k)-{i}|+|N(i)-{k}|=|S2|=6. Then S2=(N(k)-{i})∪(N(i)-{k})=N({i,k}). So, j∈N({i,k}). Thus, there always exist two nodes a,b∈V-S1-S2 such that, for nodes a,b,j, condition (1) of Lemma 5 is satisfied. Therefore, N(i)-{k}⊈S2. Let l∈N(i)-{k}, l∉S2, X={i,k,l}; we have N(X,3)⩾7. Then there exists a node m∈V-S1-S2 such that m∈N(X). We claim that (i,m)∈E. Otherwise, if (k,m)∈E or (l,m)∈E, then condition (1) of Lemma 5 is satisfied, a contradiction. Now, let Y={k,l,m}; then Y⊂N(i). This implies that any two nodes of Y are not adjacent, and by Lemma 14 we have that N(Y,3)⩾8. In other words, there exists a node q∈V-S1-S2 such that q∈N(Y). Then, for nodes i,q,l(korm), condition (1) of Lemma 5 is satisfied, a contradiction.
Case 2 (p=2). Let {i,j}=S1-S2, {i′,j′}=S2-S1, and X={i,j,i′,j′}. We have that N(X,4)⩾8 and |S1∩S2|=4, and then |N(X)|-|S1∩S2|⩾8-4=4. So, there exist four nodes a,b,c,d∈V-S1-S2 such that {a,b,c,d}⊂N(X). Let Y={a,b,c,d}; we claim that any two nodes of Y are not adjacent. Otherwise, for nodes i(jori′orj′) and the adjacent pair of Y, condition (1) of Lemma 5 is satisfied, a contradiction. By Lemma 14 we have that N(Y,4)⩾9. Thus, there exists a node k∈V-S1-S2 such that k∈N(Y). Without loss of generality, let (k,a)∈E; then, for nodes k,a,i(jori′orj′), condition (1) of Lemma 5 is satisfied, a contradiction.
Case 3 (p=3). Since |S1-S2|=|S2-S1|=p=3, let X=(S1-S2)∪(S2-S1) with |X|=6 and N(X)⩾9. Note that |S1∪S2-X|=9-6=3; then |N(X)|-|S1∪S2-X|⩾9-3=6. A similar argument to case 2 can be used in the rest.
Case 4 (p>3). Since |S1-S2|=|S2-S1|=p⩾4, there always exists a set X=(S1-S2)∪(S2-S1) with |X|=8 and NX⩾11. Note that |S1∪S2-X|⩽12-8=4; then |N(X)|-|S1∪S2-X|⩾11-4=7. A similar conclusion can be obtained by the similar analysis of case 2.
Above all, a2D mesh with n2 nodes (n⩾5) is a 6/6-diagnosable system.Furthermore, by a similar analysis to the situation of 2D mesh, we can conclude that the3D mesh with n3 nodes (n⩾4) is 10/10-diagnosable.


### 4.3. Permutation Star Graph

Ann-dimensional star graph, denoted by Sn, is a graph with the node set V(Sn)={a1a2a3⋯an|a1a2a3⋯an is a permutation of 1,2,3,⋯,n} and the edge set E(Sn)={(a1a2a3⋯an,aia2a3⋯ai-1a1ai+1⋯an)|2⩽i⩽n}. There is an edge between two nodes of Sn if and only if they can be obtained from each other by swapping the leftmost number with one of the other n-1 numbers. The cn-number of two nodes x,y is the number of common neighbors they share, denoted by cn(u,v). Let cn(Sn)=max{cn(u,v)⁡|u,v∈V}; by [15], we have cn(Sn)=1.For each adjacent pair of nodes{i,j}⊂Sn, we always have Ni,j=2n-4<2n-3. By Theorem 10, we have that the n-dimensional star graph is not (2n-3)/(2n-3)-diagnosable. Next, we shall show that an n-dimensional star graph is (2n-4)/(2n-4)-diagnosable system.Theorem 16.
Ann-dimensional(n⩾5) star graph Sn, denoted by G=(V,E), is a (2n-4)/(2n-4)-diagnosable system.Proof.
Assume that, to the contrary, ann-dimensional star graph Sn is not a (2n-4)/(2n-4)-diagnosable system. Then there exist two sets of nodes U1,U2⊆Sn with |U1|=|U2|=2n-4 and U1≠U2; we have that for U1 and U2 none of the three conditions of Lemma 5 is satisfied. Let |U1-U2|=|U2-U1|=p, 1⩽p⩽2n-4. Consider the following cases.
Case 1 (p=1). Let {i}=U1-U2, {j}=U2-U1. Since |N({i,j})|⩾2n-4 and |U1∩U2|=2n-5, there exists a node k∈V-U1-U2 such that (i,k)∈E or (j,k)∈E. Without loss of generality, let (i,k)∈E; then we have N(k)-{i}⊆U2. If N(i)-{k}⊆U2, note that (N(k)-{i})∩(N(i)-{k})=ϕ and |N(k)-{i}|+|N(i)-{k}|=|U2|=2n-4; then U2=((N(k)-{i})∪(N(i)-{k})=N({i,k}), j∈N({i,k}). Without loss of generality, let (j,k)∈E; note that cn(Sn)=1; then N(j)∈V-(U1∪U2). Let v∈N(j)-{k}, and then N(v)-{j}⊂V-(U1∪U2). In other words, there exists a node u∈N(v)-{j} such that u∈V-(U1∪U2). Then, for nodes j,u,v, condition (1) of Lemma 5 is satisfied. Therefore, N(i)-{k}⊈U2. Let l∈N(i)-{k}; then l∉U2. Let X={i,k,l}; by the definition of n-dimensional star graph, we have N(X)⩾3n-7 and |N(X)|-|U2|⩾3n-7-(2n-4)=n-3⩾2(n⩾5). Then there exists a node v∈V-U1-U2 such that v∈N(X). We claim that (v,i)∈E. Otherwise, for nodes i,v,k(l), condition (1) of Lemma 5 is satisfied, a contradiction. Letting Y={v,l,k}, since Y⊂N(i), by the definition of n-dimensional star graph, we have N(Y)⩾3n-5. Then we have |N(Y)|-|U1∪U2|⩾3n-5-(2n-3)=n-2⩾3(n⩾5). Hence, there exists a node m∈V-U1-U2 such that m∈N(Y). Without loss of generality, let (m,v)∈E; then, for nodes m,v,i, condition (1) of Lemma 5 is satisfied, a contradiction.
Case 2 (p=2). Let {i,j}=U1-U2, {i′,j′}=U2-U1 and X={i,j,i′,j′}. By the definition of star graph we know that N(X)⩾4n-10 and |U1∩U2|=2n-6. Then |N(X)|-|U1∩U2|⩾4n-10-(2n-6)=2n-4⩾4(n⩾4). There exist four nodes a,b,c,d∈V-U1-U2 such that {a,b,c,d}⊂N(X). Let Y={a,b,c,d}; then N(Y)⩾4n-10, |N(Y)|-|U1∪U2|⩾4n-10-(2n-2)=2n-8⩾2(n⩾5). Therefore, there exists a node v∈V-U1-U2 such that v∈N(Y). Without loss of generality, let (a,v)∈E; then, for nodes a,v,i, condition (1) of Lemma 5 is satisfied, a contradiction.
Case 3 (2<p<2n-4). Since |U1-U2|=|U2-U1|=p⩾3, there always exists a set X⊆(U1-U2)∩(U2-U1) with |X|=6 such that N(X)⩾6n-18. Note that |U1∪U2-X|⩽4n-9-6=4n-15 and |N(X)|-|U1∩U2-X|⩾6n-18-(4n-15)=2n-3⩾7 (n⩾5). Then there exist six nodes a,b,c,d,e,f∈V-U1-U2 and {a,b,c,d,e,f}⊂N(X). Let Y={a,b,c,d,e,f}, and then |N(Y)|-|U1∪U2|⩾6n-18-(4n-9)=2n-9⩾1(n⩾5). Therefore, there exists a node m∈V-U1-U2 such that m∈N(Y). Without loss of generality, let (a,m)∈E, then for nodes a,m,i(i∈Xandi∈N(Y)), condition (1) of Lemma 5 is satisfied, a contradiction.
Case 4 (p=2n-4). Since |U1-U2|=|U2-U1|=p=2n-4, there always exists a set X⊆(U1∪U2) with |X|=6 such that N(X)⩾6n-18. Then |N(X)|-|U1∪U2-X|⩾6n-18-(4n-14)=2n-4⩾6(n⩾5). Hence, there exists a node v∈V-U1-U2 such that v∈N(X). If there exists a node u∈N(v) such that u∈V-U1-U2, then, for nodes u,v,i(i∈X and i∈N(v)), condition (1) of Lemma 5 is satisfied, a contradiction. Thus, we have N(v)⊂(U1∪U2). Note that N(v)=n-1⩾4(n⩾5); then there must exist two nodes k,l∈N(v) such that either k,l∈U1 or k,l∈U2. Thus, for nodes v,k,l, condition (2) or (3) of Lemma 5 is satisfied, a contradiction.
Above all, ann-dimensional star graph Sn (n⩾5) is (2n-4)/(2n-4)-diagnosable system.


## 4.1.n-Dimensional Hypercube

Ann-dimensional hypercube Qn has 2n nodes and each node is labeled by an n-bit binary string. Two nodes are adjacent if and only if their labels differ in exactly one bit position [21]. Since for each adjacent pair of nodes {i,j}⊂Qn, Ni,j=2n-2<2n-1, by Theorem 10 we have that the n-dimensional hypercube is not (2n-1)/(2n-1)-diagnosable. Next, we shall show that an n-dimensional hypercube is (2n-2)/(2n-2)-diagnosable.Lemma 12 (see [22]).
LetG=(V,E) be the graph of a hypercube of n dimension and X⊂V with |X|=k, 0<k⩽n+1, then N(X)⩾kn-k(k+1)/2+1.Theorem 13.
Ann-dimensional(n⩾6) hypercube Qn, denoted by G=(V,E), is a (2n-2)/(2n-2)-diagnosable system.Proof.
Assume that, to the contrary, ann-dimensional hypercube Qn is not a (2n-2)/(2n-2)-diagnosable system. Then there exist two sets of nodes S1,S2⊆Qn with |S1|=|S2|=2n-2 and S1≠S2, such that none of the three conditions of Lemma 5 is satisfied. Let |S1-S2|=|S2-S1|=p, 1⩽p⩽2n-2. Consider the following cases.
Case 1 (p=1). Let {i}=S1-S2, {j}=S2-S1. Since |N({i,j})|⩾2n-2 and |S1∩S2|=2n-3, there exists a node k∈V-S1-S2 such that (i,k)∈E or (j,k)∈E. Without loss of generality, let (i,k)∈E; then N(k)-{i}⊆S2. Otherwise there exists a node v∈V-S1-S2 such that the three nodes i, j, and k satisfy condition (1) of Lemma 5, a contradiction. We claim that N(i)-{k}⊈S2. Otherwise, note that (N(k)-{i})∩(N(i)-{k})=ϕ and |N(k)-{i}|+|N(i)-{k}|=|S2|=2n-2. Combining the address structure of Qn(n⩾6), we have that there exist two nodes a,b∈V-S1-S2 such that for nodes a,b,j, condition (1) of Lemma 5 is satisfied. Therefore N(i)-{k}⊈S2. Let l∈N(i)-{k} and l∉S2. Let X={i,k,l}; we have |N(X)|⩾3n-5. So, |N(X)|-|S2|⩾3n-5-(2n-2)=n-3⩾3(n⩾6). Without loss of generality, let v∈N(X) and v∉S2. We claim that v∈N(i). Otherwise, for nodes v,i,k(l), condition (1) of Lemma 5 is satisfied. Thus, v∈N(i); then let Y={v,l,k}, according to Lemma 12, we have |N(Y)|⩾3n-5. Let η=|N(X)|-|S1∪S2|⩾3n-5-(2n-1)=n-4. When n⩾6, we have η⩾2. Without loss of generality, let u∈N(Y) and u∉(S1∪S2). Then for nodes u,i,k(lorv), condition (1) of Lemma 5 is satisfied, a contradiction.
Case 2 (p=2). Let {i,j}=S1-S2, {i′,j′}=S2-S1, and X={i,j,i′,j′}. By Lemma 12 we know that N(X)⩾4n-9 and |S1∩S2|=2n-4. |N(X)|-|S1∩S2|⩾4n-9-(2n-4)=2n-5⩾7(n⩾6). Let Y={a,b,c,d} with Y⊂N(X) and Y∩(S1∩S2)=ϕ. According to Lemma 12, we have |N(Y)|⩾4n-9, |N(X)|-|S1∪S2|⩾4n-9-2n=2n-9⩾3(n⩾6). Thus, there exists a node v such that v∈N(Y) and v∉(S1∪S2). Without loss of generality, let (a,i)∈E and (a,v)∈E. Then, for nodes a,v,i, condition (1) of Lemma 5 is satisfied, a contradiction.
Case 3 (3⩽p⩽2n-7). Since |S1-S2|=|S2-S1|=p(3⩽p⩽2n-7), there always exists a set X⊆(S1-S2)∪(S2-S1) with |X|=6 such that N(X)⩾6n-20. Note that |S1∪S2-X|⩾4n-9-6=4n-15 and |N(X)|-|S1∪S2-X|⩾6n-20-(4n-15)=2n-5⩾7(n⩾6). Then there exists a set Y={a,b,c,d,e,f,g} such that Y⊂N(X) and Y∩(S1∪S2)=ϕ. According to Lemma 12, we have N(Y)⩾6n-20. |N(Y)|-|S1∪S2|⩾6n-20-(2n-2+p)⩾4n-18-p⩾4n-18-(2n-7)=2n-11⩾1(n⩾6). Thus, there exists a node v such that v∈N(Y) and v∉(S1∪S2). Without loss of generality, let i∈X, (a,i)∈E, and (a,v)∈E. Then for nodes a,v,i, condition (1) of Lemma 5 is satisfied, a contradiction.
Case 4 (2n-6⩽p⩽2n-2). Since |S1-S2|=|S2-S1|=p, when n⩾6, we have p⩾6. Then there always exists a set X⊆(S1-S2) with |X|=6 such that N(X)⩾6n-20. |N(X)|-|S1∪S2-X|⩾6n-20-(4n-10)=2n-10⩾2(n⩾6). Then there exists a set Y={a,b}⊂N(X) such that Y∩(S1∪S2)=ϕ. According to Lemma 12, we have N(Y)⩾2n-2. |N(Y)|-|S1∩S2|⩾2n-2-4=2n-6⩾6(n⩾6). Thus, there exists a set Z⊂N(Y) with |Z|=3 such that Z⊂S1-S2 or Z⊂S2-S1. Note that Z⊂N(Y), |Z|=3 and Y⊂N(Z), |Y|=2. Thus, there must exist one node in Y connecting two nodes in Z. Without loss of generality, let i,j∈Z, (a,i)∈E, and (a,j)∈E; then, for nodes a,i,j, condition (2) of Lemma 5 is satisfied, a contradiction.
Above all, ann-dimensional (n⩾6) hypercube Qn is a (2n-2)/(2n-2)-diagnosable system.


## 4.2.2D and 3D Mesh

A2D mesh contains n2 nodes and each node is labeled with a two-bit string such as aij(0⩽i⩽n-1,0⩽j⩽n-1). Two nodes aij and ai′j′ are adjacent if and only if one of the following conditions is satisfied.(i)
i+1modn=i′ and j=j′.(ii)
(i-1)modn=i′ and j=j′.(iii)
(j+1)modn=j′ and i=i′.(iv)
(j-1)modn=j′ and i=i′.LetG=(V,E) be the graph of a 2D mesh with n2 nodes and X⊂V with |X|=k, 0<k⩽(n-1)2; let N(X,k) denote the value of |N(X)|.Observe thatN(X,2)⩾6, N(X,3)⩾7, N(X,4)⩾8, N(X,6)⩾9, and N(X,8)⩾11.Lemma 14.
LetG=(V,E) be the graph of a 2D mesh with n2 nodes, X⊂V; if any two nodes of X are not adjacent, then N(X,3)⩾8, N(X,4)⩾9, N(X,6)⩾13.Proof.
Using exhaustive method, we can easily get that the conclusion is true.For each adjacent pair of nodes{i,j}⊂V, we always have Ni,j=6<7, by Theorem 10 we have that the 2D mesh with n2 nodes is not 7/7-diagnosable. Next, we shall show that a 2D mesh with n2 nodes is a 6/6-diagnosable system.Theorem 15.
A2D mesh with n2 nodes (n⩾5), denoted by G=(V,E), is a 6/6-diagnosable system.Proof.
Assume that, to the contrary, a2D mesh with n2 nodes, denoted by G=(V,E), is not a 6/6-diagnosable system. Then there exist two sets of nodes S1,S2⊂V with |S1|=|S2|=6 and S1≠S2, such that for S1 and S2 none of the three conditions of Lemma 5 is satisfied. Let |S1-S2|=|S2-S1|=p, 1⩽p⩽6. Consider the following cases.
Case 1 (p=1). Let {i}=S1-S2, {j}=S2-S1. Since |N({i,j})|⩾6 and |S1∩S2|=5, there exists a node k∈V-S1-S2 such that (i,k)∈E or (j,k)∈E. Without loss of generality, let (i,k)∈E; then we have N(k)-{i}⊆S2. If N(i)-{k}⊆S2, note that (N(k)-{i})∩(N(i)-{k})=ϕ; this implies that |N(k)-{i}|+|N(i)-{k}|=|S2|=6. Then S2=(N(k)-{i})∪(N(i)-{k})=N({i,k}). So, j∈N({i,k}). Thus, there always exist two nodes a,b∈V-S1-S2 such that, for nodes a,b,j, condition (1) of Lemma 5 is satisfied. Therefore, N(i)-{k}⊈S2. Let l∈N(i)-{k}, l∉S2, X={i,k,l}; we have N(X,3)⩾7. Then there exists a node m∈V-S1-S2 such that m∈N(X). We claim that (i,m)∈E. Otherwise, if (k,m)∈E or (l,m)∈E, then condition (1) of Lemma 5 is satisfied, a contradiction. Now, let Y={k,l,m}; then Y⊂N(i). This implies that any two nodes of Y are not adjacent, and by Lemma 14 we have that N(Y,3)⩾8. In other words, there exists a node q∈V-S1-S2 such that q∈N(Y). Then, for nodes i,q,l(korm), condition (1) of Lemma 5 is satisfied, a contradiction.
Case 2 (p=2). Let {i,j}=S1-S2, {i′,j′}=S2-S1, and X={i,j,i′,j′}. We have that N(X,4)⩾8 and |S1∩S2|=4, and then |N(X)|-|S1∩S2|⩾8-4=4. So, there exist four nodes a,b,c,d∈V-S1-S2 such that {a,b,c,d}⊂N(X). Let Y={a,b,c,d}; we claim that any two nodes of Y are not adjacent. Otherwise, for nodes i(jori′orj′) and the adjacent pair of Y, condition (1) of Lemma 5 is satisfied, a contradiction. By Lemma 14 we have that N(Y,4)⩾9. Thus, there exists a node k∈V-S1-S2 such that k∈N(Y). Without loss of generality, let (k,a)∈E; then, for nodes k,a,i(jori′orj′), condition (1) of Lemma 5 is satisfied, a contradiction.
Case 3 (p=3). Since |S1-S2|=|S2-S1|=p=3, let X=(S1-S2)∪(S2-S1) with |X|=6 and N(X)⩾9. Note that |S1∪S2-X|=9-6=3; then |N(X)|-|S1∪S2-X|⩾9-3=6. A similar argument to case 2 can be used in the rest.
Case 4 (p>3). Since |S1-S2|=|S2-S1|=p⩾4, there always exists a set X=(S1-S2)∪(S2-S1) with |X|=8 and NX⩾11. Note that |S1∪S2-X|⩽12-8=4; then |N(X)|-|S1∪S2-X|⩾11-4=7. A similar conclusion can be obtained by the similar analysis of case 2.
Above all, a2D mesh with n2 nodes (n⩾5) is a 6/6-diagnosable system.Furthermore, by a similar analysis to the situation of 2D mesh, we can conclude that the3D mesh with n3 nodes (n⩾4) is 10/10-diagnosable.


## 4.3. Permutation Star Graph

Ann-dimensional star graph, denoted by Sn, is a graph with the node set V(Sn)={a1a2a3⋯an|a1a2a3⋯an is a permutation of 1,2,3,⋯,n} and the edge set E(Sn)={(a1a2a3⋯an,aia2a3⋯ai-1a1ai+1⋯an)|2⩽i⩽n}. There is an edge between two nodes of Sn if and only if they can be obtained from each other by swapping the leftmost number with one of the other n-1 numbers. The cn-number of two nodes x,y is the number of common neighbors they share, denoted by cn(u,v). Let cn(Sn)=max{cn(u,v)⁡|u,v∈V}; by [15], we have cn(Sn)=1.For each adjacent pair of nodes{i,j}⊂Sn, we always have Ni,j=2n-4<2n-3. By Theorem 10, we have that the n-dimensional star graph is not (2n-3)/(2n-3)-diagnosable. Next, we shall show that an n-dimensional star graph is (2n-4)/(2n-4)-diagnosable system.Theorem 16.
Ann-dimensional(n⩾5) star graph Sn, denoted by G=(V,E), is a (2n-4)/(2n-4)-diagnosable system.Proof.
Assume that, to the contrary, ann-dimensional star graph Sn is not a (2n-4)/(2n-4)-diagnosable system. Then there exist two sets of nodes U1,U2⊆Sn with |U1|=|U2|=2n-4 and U1≠U2; we have that for U1 and U2 none of the three conditions of Lemma 5 is satisfied. Let |U1-U2|=|U2-U1|=p, 1⩽p⩽2n-4. Consider the following cases.
Case 1 (p=1). Let {i}=U1-U2, {j}=U2-U1. Since |N({i,j})|⩾2n-4 and |U1∩U2|=2n-5, there exists a node k∈V-U1-U2 such that (i,k)∈E or (j,k)∈E. Without loss of generality, let (i,k)∈E; then we have N(k)-{i}⊆U2. If N(i)-{k}⊆U2, note that (N(k)-{i})∩(N(i)-{k})=ϕ and |N(k)-{i}|+|N(i)-{k}|=|U2|=2n-4; then U2=((N(k)-{i})∪(N(i)-{k})=N({i,k}), j∈N({i,k}). Without loss of generality, let (j,k)∈E; note that cn(Sn)=1; then N(j)∈V-(U1∪U2). Let v∈N(j)-{k}, and then N(v)-{j}⊂V-(U1∪U2). In other words, there exists a node u∈N(v)-{j} such that u∈V-(U1∪U2). Then, for nodes j,u,v, condition (1) of Lemma 5 is satisfied. Therefore, N(i)-{k}⊈U2. Let l∈N(i)-{k}; then l∉U2. Let X={i,k,l}; by the definition of n-dimensional star graph, we have N(X)⩾3n-7 and |N(X)|-|U2|⩾3n-7-(2n-4)=n-3⩾2(n⩾5). Then there exists a node v∈V-U1-U2 such that v∈N(X). We claim that (v,i)∈E. Otherwise, for nodes i,v,k(l), condition (1) of Lemma 5 is satisfied, a contradiction. Letting Y={v,l,k}, since Y⊂N(i), by the definition of n-dimensional star graph, we have N(Y)⩾3n-5. Then we have |N(Y)|-|U1∪U2|⩾3n-5-(2n-3)=n-2⩾3(n⩾5). Hence, there exists a node m∈V-U1-U2 such that m∈N(Y). Without loss of generality, let (m,v)∈E; then, for nodes m,v,i, condition (1) of Lemma 5 is satisfied, a contradiction.
Case 2 (p=2). Let {i,j}=U1-U2, {i′,j′}=U2-U1 and X={i,j,i′,j′}. By the definition of star graph we know that N(X)⩾4n-10 and |U1∩U2|=2n-6. Then |N(X)|-|U1∩U2|⩾4n-10-(2n-6)=2n-4⩾4(n⩾4). There exist four nodes a,b,c,d∈V-U1-U2 such that {a,b,c,d}⊂N(X). Let Y={a,b,c,d}; then N(Y)⩾4n-10, |N(Y)|-|U1∪U2|⩾4n-10-(2n-2)=2n-8⩾2(n⩾5). Therefore, there exists a node v∈V-U1-U2 such that v∈N(Y). Without loss of generality, let (a,v)∈E; then, for nodes a,v,i, condition (1) of Lemma 5 is satisfied, a contradiction.
Case 3 (2<p<2n-4). Since |U1-U2|=|U2-U1|=p⩾3, there always exists a set X⊆(U1-U2)∩(U2-U1) with |X|=6 such that N(X)⩾6n-18. Note that |U1∪U2-X|⩽4n-9-6=4n-15 and |N(X)|-|U1∩U2-X|⩾6n-18-(4n-15)=2n-3⩾7 (n⩾5). Then there exist six nodes a,b,c,d,e,f∈V-U1-U2 and {a,b,c,d,e,f}⊂N(X). Let Y={a,b,c,d,e,f}, and then |N(Y)|-|U1∪U2|⩾6n-18-(4n-9)=2n-9⩾1(n⩾5). Therefore, there exists a node m∈V-U1-U2 such that m∈N(Y). Without loss of generality, let (a,m)∈E, then for nodes a,m,i(i∈Xandi∈N(Y)), condition (1) of Lemma 5 is satisfied, a contradiction.
Case 4 (p=2n-4). Since |U1-U2|=|U2-U1|=p=2n-4, there always exists a set X⊆(U1∪U2) with |X|=6 such that N(X)⩾6n-18. Then |N(X)|-|U1∪U2-X|⩾6n-18-(4n-14)=2n-4⩾6(n⩾5). Hence, there exists a node v∈V-U1-U2 such that v∈N(X). If there exists a node u∈N(v) such that u∈V-U1-U2, then, for nodes u,v,i(i∈X and i∈N(v)), condition (1) of Lemma 5 is satisfied, a contradiction. Thus, we have N(v)⊂(U1∪U2). Note that N(v)=n-1⩾4(n⩾5); then there must exist two nodes k,l∈N(v) such that either k,l∈U1 or k,l∈U2. Thus, for nodes v,k,l, condition (2) or (3) of Lemma 5 is satisfied, a contradiction.
Above all, ann-dimensional star graph Sn (n⩾5) is (2n-4)/(2n-4)-diagnosable system.


## 5. Experiments and Comparisons

Diagnosability plays an important role in the reliability of an interconnection network. For an interconnection network, the larger the diagnosability it has, the stronger the self-diagnostic capability it has. In this section, we show that thet/t-diagnosable strategy proposed in the paper is superior to the traditional t-diagnosable strategy by comparing t/t-diagnosability and t-diagnosability for the hypercube networks (the star networks).For the sake of convenience, lett(Qn) (respectively, t/t(Qn)) represent the t-diagnosability (respectively, t/t-diagnosability) of n-dimensional hypercube networks and t(Sn) (respectively, t/t(Sn)) represent the t-diagnosability (respectively, t/t-diagnosability) of n-dimensional star networks. According to [11], it is easily obtained that t(Qn)=n,t(Sn)=n-1. By Theorem 10 and Theorem 13, we have that t/t(Qn)=2n-2,t/t(Sn)=2n-4. This implies that that the t/t-diagnosability of n-dimensional hypercube network is 2n-2 which is almost twice as large as n, t-diagnosability of Qn, and t/t-diagnosability of Sn is 2n-4 which is almost twice as large as n, the t-diagnosability of Sn. In order to compare expediently their sizes, we have made a table (namely, Table 1) for 5⩽n⩽15. By Table 1, it is easily found that for each n⩾5 the number of Colum 3 (t/t(Qn) is larger than the number of Column 1 (t(Qn)), and the number of Column 4 (t/t(Sn) is larger than the number of Column 3 (t(Sn)). For example, n=14, t/t(Qn)=26 is 12 more than 14, t(Qn), and t/t(Sn)=24 is 11 more than 13, t(Sn). In order to compare the growth trend of t-diagnosability and t/t-diagnosability for hypercube network and star network for variable n, we have made Figures 3 and 4, where Figure 3 illustrates the growth trend of t-diagnosability and t/t-diagnosability for hypercube network, and Figure 4 illustrates the growth trend of t-diagnosability and t/t-diagnosability for star network. Figures 3 and 4 and the data in Table 1 show that, for an n-dimensional interconnection network, our diagnostic strategy is superior to the classical t-diagnosable strategy proposed by [11]. For example, for a 10-dimensional hypercube network, when there are more than 10 faulty nodes in the system, the classical t-diagnosable strategy proposed by [11] does not work. However, our t/t-diagnosable strategy proposed in this paper still works provided the number of faulty nodes in the network does not exceed 18.Table 1
Comparison of classical diagnosability andt/t-diagnosability of n-dimensional hypercube and star network.
n t ( Q n ) t/t(Qn) t(Sn) t/t(Sn) 5 5 8 4 6  6 6 10 5 8  7 7 12 6 10  8 8 14 7 12  9 9 16 8 14  10 10 18 9 16  11 11 20 10 18  12 12 22 11 20  13 13 24 12 22  14 14 26 13 24  15 15 28 14 26Figure 3
Comparison of classical diagnosability andt/t-diagnosability of n-dimensional hypercube networks.Figure 4
Comparison of classical diagnosability andt/t-diagnosability of n-dimensional star networks.


## 6. Conclusion

This paper proposes characterizations oft/t-diagnosable systems under the comparison model. By analyzing characterizations of t/t-diagnosable systems we discover some properties of allowable fault set, which are significant in exploring the AFS in a system under the comparison model. Furthermore, we also introduce a method to find out a range from tmin to tmax, in which the system is at least tmin/tmin-diagnosable and at most tmax/tmax-diagnosable. Also by using above method and the characterization of t/t-diagnosable systems we figure out the t/t-diagnosability of some practical interconnection networks such as n-dimensional hypercube, 2D (3D) mesh, and n-dimensional permutation star graph.



---

*Source: 7168628-2018-06-14.xml*