Abstract

In a multiprocessor systems, it is important to local and to replace the faulty processors to maintain systempsilas high reliability. The fault diagnosis, which is the process of identifying fault processors in a multiprocessor system through testing. The conditional diagnosis requires that for each processor u in a system, all the processors that are directly connected to u do not fail at the same time. In this paper, we study the conditional diagnosability of the n-dimensional locally twisted cubes. After showing some properties of the locally twisted cubes, we prove that it under the PMC model is 4n – 7 for n ≥ 5.

1. Introduction

In recent years, the number of the processors in a multiprocessor system increases as fast as the technology development. Thus some processors may fail in such a multiprocessor operating system. So locating the faulty processors is important for system maintenance and dependable computing. System level diagnosis is an important approach for fault diagnosis in a multiprocessor system. Many different models for system level diagnosis in multiprocessor systems have been proposed, e.g., the PMC (the Perfect Minicomputer Corporation) model [1], the comparison model [2] and the BGM model [3]. So far, the well-studied mode is the PMC model introduced by Preparata, Metze, and Chien [1].

A multiprocessor system is an interconnected collection of processors and can be represented by an undirected graph G = (V, E), where each vertex of the vertex set V represents a processor and each edge of the edge set E represents a communication link between a pair of processors. Two processors interact with each other by sending messages over the communication link. Under the PMC model, two processors can test each other if and only if there is a link between them. The processor which tests the status of the other is called a tester. It is assumed that the test result is reliable if and only if the tester is fault free; otherwise, the test result is unreliable. The collection of all test results is called a syndrome·r(u, v) denotes the test result of processor u testing processor v. If v pass the test executed by u, r(u, v) = 0; otherwise, r(u, v) = 1. Table 1 shows all possible test results of the test r(u, v).

For a given syndrome, a subset of vertices is said to be consistent with if can arise from the circumstance that all nodes in F are faulty and all nodes in V-F are fault free. It is worth pointing out that a given set F of faulty vertices may be consistent with different syndromes. Let be the set containing all syndromes which can be produced by F. Two distinct sets F₁, are said to be distinguishable if otherwise, F₁, F₂ are said to be indistinguishable.

A system is said to be t-diagnosable if given a syndrome, all processors can correctly be identified faulty or faulty free, provided that the number of faulty processors present in the system does not exceed t. The diagnosability of a system is the maximal number of faulty processors that the system can guarantee to diagnose. The diagnosability of some interconnection networks have been discussed under the PMC model, see [4-6].

Lai et al. in [7] introduced conditional diagnosability by restricting that for each processor u in a system, all processors adjacent to u are not faulty at the same time, and showed that conditional diagnosability of the n-dimensional hypercube (Q_n) is 4n – 7 for n ≥ 5, which is about four times as large as its classical diagnosability [8]. Zhu et al. in [9] presented that under PMC-model the conditional diagnosability of FQn (t_c(FQ_n)) was 4n – 3 when n ≥ 5 or n > 8; t_c(FQ₃) = 3, t_c(FQ₄) = 7.

In recent years, conditional diagnosability of several interconnection networks has also been explored under the PMC model [7,9-12].

In the paper, we prove that conditional diagnosability of locally twisted cubes under the PMC model is

The rest of paper is organized as follows: Preliminary knowledge is provided in Section 2; The main results of this paper are presented and proven in Section 3; The conclusions are made in Section 4.

2. Preliminaries

For all the terminologies and notations not defined here, we follow [13]. For a graph G = (V, E) and S Ì V(G) or S Ì G, we use N_G(S) to denote the set of neighboring vertices of S in G-S, when it is easy to know from the context what G denotes, it is usually simplified with N(S). We use A_G(S) to denote the union of S and N_G(S). And similarly A_G(S) can be simplified with A(S).

That is, N_G(S) = {vÎ V (G)-S|$ u ÎS such that (u, v) Î E(G)}, A_G(S) = N_G(S) S.

We use d_G(u) to denote the degree of u in G and d_G(u) can be simplified with d(u).

Definition 1. [14] For n ≥ 2, an n-dimensional locally twisted cube, denoted by LTQ_n, is defined recursively as follows:

1) LTQ₂ is a graph consisting of four nodes labeled with 00, 01, 10 and 11, respectively, connected by four edges {00, 01}, {01, 11},{11, 10} and {10, 00}.

2) For n ≥ 3, LTQ_n is built from two disjoint copies of LTQ_n–1 according to the following steps: Let 0LTQ_n–1 denote the graph obtained from one copy of LTQ_n–1 by prefixing the label of each node with 0. Let 1LTQ_n–1 denote the graph obtained from the other copy of LTQ_n–1 by prefixing the label of each node with 1. Connect each node of 0LTQn 1 to the node of 1LTQ_n 1 with an edge, where “+” represents the modulo 2 addition.

Figure 1 shows two examples of locally twisted cubes. The locally twisted cubes can also be equivalently defined in the following non-recursive fashion.

Definition 2. [14] For n ≥ 2, the n-dimensional locally twisted cube, LTQ_n, is a graph with {0, 1}ⁿ as the node set. Two nodes and of LTQ_n are adjacent if and only if either one of the following conditions are satisfied.

1) and x_i+1 = y_i+1 + y_n for some 1 £ i £ n – 2, and x_j = y_j for all the remaining bits;

2) for i Î {n – 1, n}, and x_j = y_j for all the remaining bits.

The definition of the conditional diagnosability is as follows.

Definition 3. [7] A faulty set F Í V is called a conditional faulty set if N(v) Ë F for any vertex v Î V. A system G(V, E) is conditionally t-diagnosable if F₁ and F₂ are distinguishable, for each pair of conditional faulty sets F₁, F₂ Í V , and F₁ ¹ F₂ with |F₁|; |F₂| £ t. Conditional diagnosability of a system G, written as t_c(G) is defined to be the maximum value of t such that G is conditionally t-diagnosable.

Let F₁, F₂ be two distinct sets, the symmetric difference of F₁ and F₂ is denoted by F₁DF₂, that is, F₁DF₂ = (F₁ – F₂) È (F₂ – F₁). The following lemma proposed by Dahbura and Masson [15] gives a necessary and sufficient condition for a system to be t-diagnosable.

Lemma 1. [16] A system G(V, E) is t-diagnosable if and only if, for each pair F, F₂ Ì V with|F₁|, |F₂| £ t and F₁ ¹ F₂, there is at least one test from V – F₁ È F₂ to F₁DF₂.

Lemma 2. [14] k(LTQ_n) = n for n ≥ 2.

Lemma 3. [17] k (LTQ_n) = 2n – 2 for n ≥ 3.

Lemma 4. [17] Let S be a set of vertices S Ì V(LTQ_n) with |S| = n, if LTQ_n-S is disconnected, there exists a vertex u Î V(V(LTQ_n)) such that N(u) = S for n ≥ 2.

The following lemma is derived based on [18,19].

Lemma 5. Let F be a subgraph of LTQ_n with

, we have.

3. Conditionally Diagnosability

Lemma 6. Let S be a set of vertices S Ì V(LTQ_n) and n ≥ 3. Suppose that LTQ_n – S is disconnected. The following two conditions hold:

(1) |S| ≥ n;

(2) If n £ |S| £ 2n – 3, then LTQ_n-S has exactly two components, one is trivial and the other is nontrivial. The nontrivial component of LTQ_n-S contains 2ⁿ– |S| – 1 vertices.

Proof: By lemma 2 k(LTQ_n) = n, so condition (1) holds. We need to prove that condition (2) is true. Since is disconnected, there are at least two components in. We will prove that |S| ≥ 2n – 2 when contains at least two trivial components or two nontrivial components. It implies that n £ |S| £ 2n – 3 when contains a trivial components and nontrivial components.

Case 1. contains at least two trivial components. Let u₁, u₂ Î V(LTQ_n) and {u₁}, {u₂} be two trivial components. Then N(u₁) Ì S and N(u₂) Ì S. Since any two distinct vertices of a LTQ_n have at most two common neighbors, we have |N(V₁) |N(V₂)| £ 2.

Hence, |S | ≥ |N(V₁)| + |N(V₂)| – |N(V₁) N(V₂)| ≥ 2n + 2n – 2 = 2(2n – 1).

Case 2. LTQ_n-S contains at least two nontrivial components. We prove condition (2) by induction on n. Suppose n £ |S| £ 2n – 3, it is easy to see that |S| = 3 for n = 3. The connectivity of LTQ₃ is 3. By Lemma 4, there exist a vertex u Î V (LTQ₃) such that S = N(u) Thus LTQ₃-S has exactly two components: one is trivial and the other is nontrivial. Therefore, if LTQ₃-S has at least two nontrivial components, |S| ≥ 2n – 2, where n = 3. Assume that the result holds for all n – 1, n – 1 ≥ 3. In the following we show that it holds for n.

Let S₀ = S V(0LTQ_n–1) and S₁ = S V (1LTQ_n–1), F and F' be two nontrivial component of LTQ_n-S. So |V(F)| ≥ 2 and |V(F′)| ≥ 2.

We consider the following three cases:

Case 2.1. F, F′ Í 0LTQ_n–1 or F, F′ Í 1LTQ_n–1. Without loss of generality, let F, F′ Í 0LTQ_n–1 , then 0LTQ_n-1 -S₀ is disconnected and|S₁| ≥ |F| +|F′| ≥ 4. So |S₀| ≥ k₂ = 2n – 4 by lemma 3. Thus |S| = |S₀| + |S₁| ≥ 2n – 2.

Case 2.2. F Í 0LTQ_n–1 and F′ Í 1LTQ_n–1, or F′ Í 1LTQ_n–1 and F Í 1LTQ_n–1. Without loss of generality, let F Í 0LTQ_n–1 and F′ Í 1LTQ_n–1. If both 0LTQ_n–1 – S₀ and 1LTQ_n–1 – S₁ are connected, then |S₀| ≥ 2n – 4 and S₁| ≥ 2n – 4. So |S| = |S₀| + |S₁| ≥ 2n – 4 + 2n– 4 ≥ 2n – 2 for n ≥ 3. If exactly one of 0LTQ_n–1 – S₀ and 1LTQ_n–1 – S₁ is disconnected, let 0LTQ_n–1 – S₀ be disconnected, then Í S₀. So

Case2.3. 0LTQ_n–1 and 1LTQ_n–1 , or 0LTQ_n–1 and 1LTQ_n–1 . Without loss of generality, let 0LTQ_n–1 and 1LTQ_n-1 . Since there is another component F′ of LTQ_n  – S, at least one of the two graphs 0LTQ_n–1 –  S₀ and 1LTQ_n–1 – S₁ is disconnected. So we drive the result by consider two Subcase.

Case 2.3.1. Both 0LTQ_n–1 – S₀ and 1LTQ_n–1 – S₁ are disconnected. Since k(LTQ_n–1) = n – 1, |S₀| ≥ n – 1 and|S₁| ≥ n – 1. Then |S| = |S₀| + |S₁|≥ 2n – 2.

Case 2.3.2. Exactly one of the two subgraphs 0LTQ_n–1 – S₀ and 1LTQ_n–1 – S₁ is disconnected. Without loss of generality, assume that 0LTQ_n–1 – S₀ is connected and 1LTQ_n–1 – S₁ is disconnected. Then |S₁| ≥ n – 1 and N_0LTQn(F) Í S₀. Hence, |S₀| ≥ |V(F′)| ≥ 2. If |S₁| ≥ 2n – 4, then |S| = |S₀| + |S₁| ≥ 2 + (2n – 4) = 2n – 2. Otherwise, n – 2 £ |S₁| £ 2n – 5. By induction hypothesis, 1LTQ_n–1 – S₁ has exactly two components: one is trivial and the other is nontrivial. We know that 1LTQ_n–1 F and F′ are two components of 1LTQ_n–1 – S₁, and F′ is a nontrivial component. Thus 1LTQ_n–1 F must be a trivial component of 11LTQ_n–1 – S₁, and |V(F′)| = 2^n–1 – |S₁| – 1. Note that N_0LTQn(F′) Í S₀. Hence, |S| = |S₀| + |S₁| ≥ |V(F′)| + |S₁| = 2^n–1 – |S₁| – 1 + |S₁| ≥ 2n – 2 for n ≥ 4.

Consequently, condition (2) holds.■

Lemma 7: Let S be a set of vertices S Ì V(LTQ_n) and n ≥ 5. Suppose that LTQ_n-S is disconnected and every component of LTQ_n-S is nontrivial, and there exists one component F of LTQ_n-S such that d_F (v) ≥ 2 for any vertex v Î F. Then one of the following two conditions must hold:

(1) |S| ≥ 4n – 8;

(2) |V(F)| ≥ 4n – 9.

Proof: Let F₀ = 0LTQ_n–1 F, F₁ = 1LTQ_n–1 F, S₀. = S V(0LTQ_n–1) and S₁ = S V(1LTQ_n–1). We consider two cases: (a) F Ì 0LTQ_n–1 or F Ì 1LTQ_n–1. (b) 0LTQ_n–1 and 1LTQ_n–1 .

Case 1. F Ì 0LTQ_n–1 or F Ì 1LTQ_n–1. Without loss of generality, let F Ì 0LTQ_n–1. Then F Ì S₁. In the following we consider two cases.

Case 1.1. 0LTQ_n–1-F is connected. Then |S| = |S₀| + |S₁| ≥ |S₀| + |V(F)| = 2^n–1 ≥ 2n – 2 for n ≥ 4 and conditional (a) holds.

Case 1.2. 0LTQ_n–1 – F is disconnected. If 4 £ |V(F)| £ 3n – 5, by Lemma 5, we have |S₀| ≥ || ≥ 4n – 8.Therefore, |S| ≥ 4n – 8 and conditional (a) holds. If 3n – 4 £ |V(F)| £ 4n – 10, then |S₀| ≥ n – 1 since 0LTQ_n–1 – F is disconnected and |S₁| ≥ |V(F)| ≥ 3n – 4. Thus |S| = |S₀| + |S₁| ≥ n – 1 + 3n – 4 = 4n – 5 and conditional (a) holds. Otherwise, |V(F)| ≥ 4n – 9 and conditional (b) holds.

Case 2. 0LTQ_n–1 and 1LTQ_n–1. Since every vertex x in F₀ (resp. y in F₁) has at most one neighbor in F₁(resp. F₀), we have and. Since LTQ_n – S is disconnected, there are at least two components in LTQ_n – S. At least one of the two graphs 0LTQ_n–1 – S₀ and 1LTQ_n–1 – S₁ is disconnected since both LTQ_n and LTQ_n–1 contain some non-empty part of the component F.

In the following we drive the result by consider two cases.

Case 2.1. Exactly one of the two graphs 0LTQ_n–1 – S₀ and 1LTQ_n–1 – S₁ is disconnected. Without loss of generality, assume that 0LTQ_n–1 – S₀ is connected and 1LTQ_n–1 – S₁ is disconnected. Let F′ be another non-trivial component of LTQ_n – S other than F. Then and. Note that both and are nontrivial component. By Lemma 6, |S₁| ≥ 2n – 4. If j|S₀| ≥ 2n – 4, then |S| = |S₀| + |S₁| ≥ 4n – 8 and condition (1) holds. Otherwise, |S₀| £ 2n – 5. Then=since = S₀V (F₀).

Thereby, |V(F)| = |V(F₀)|+|V(F₁)| ≥+ 2 ≥ 4n – 9 for n ≥ 4 and condition (2) holds.

0LTQ_n–1 – S₀ and 1LTQ_n–1 – S₁ are disconnected. We consider the following three subcases.

Case 2.1.1. |S₀| ≥ 2n – 4 and |S₁| ≥ 2n – 4.Clearly, S| = |S₀| + |S₁| ≥ 8n – 8. Therefore, condition (1) holds.

Case 2.2.2. Either n – 1 £ |S₀| £ 2n – 5, |S₁| ≥ 2n – 4 or |S₀| ≥ 2n – 4, n – 1 £ | S₁| £ 2n – 5. Without loss of generality, assume that S₀| ≥ 2n – 4, n – 1 £ | S₁| £ 2n – 5. Then we have | V(F₁)| = 2^n–1 – |S₁| – 1 by the lemma 6. Since for any vertex u V (F₀),|V(F₀)| ≥ 2. Thus, |V(F)| = |V(F₀)| + |V(F₁)| ≥ 2 + ≥ 4n – 9 for n ≥ 5. Hence, condition (2) holds.

Case 2.2.3. n – 1 £ | S₀| £ 2n – 5 and n – 1 £ | S₁| £ 2n – 5. By the lemma 6, we have |V(F₀)| = 2^n–1 – |S₀| – 1 and |V (F₁)| = 2^n–1 – |S₁| – 1. So |V(F)| = |V(F₀)| + |V (F₁)| = 2ⁿ – |S| – 2. If |S| ≥ 4n – 8, then condition (1) holds. Otherwise, |S| £ 4n – 9, then |V (F)| = 2ⁿ – (4n – 9) – 2 ≥ 4n – 9 for n ≥ 4. Hence, condition (2) holds.

Consequently, the lemma holds. ■

Theorem 1. Let F₁, F₂ Ì be two indistinguishable conditional faulty sets, then either |F₁| ≥ 4n – 6 or |F₂| ≥ 4n – 6 for n ≥ 5.

Proof: Let S = F₁ F₂, according to LTQ_n – S is connected or not, we consider the following two cases.

Case 1. LTQ_n – S is connected. We assert that F₀DF₁ = V (LTQ_n) – S. Otherwise, suppose u ÎV(LTQ_n – S) – F₁DF₂ = V (LTQ_n) – F₁ F₂.Then u is connected to F₁DF₂ since LTQ_n – S is connected. That is, there is an edge between F₁DF₂ and V – F₁ F₂. This is a contradiction to the fact F₁ and F₂ are an indistinguishable. Since |F₁| + |F₂| = |F₁|D|F₂| = |V(LTQ_n)| = 2ⁿ ≥ 8n – 13 for n ≥ 5, either |F₁| ≥ 4n – 6 or |F₂| ≥ 4n – 6. Then the result follows.

Case 2. LTQ_n – S is disconnected. Since F₁ and F₂ is indistinguishable, there is no edge between F₁DF₂ and V (LTQ_n) – F₁F₂ by Lemma 1.That is, for any vertex u F₁ D F_2, Ì F₁ F₂. Since both F₁and F₂ are conditional faulty set, Ë F₁and

and.

Thus for any vertex u F₁ D F₂ , || ≥ 2. So LTQ_n – S has a component P with V (P) Ì F₁ D F₂ such that d_P(u) ≥ 2 for any vertex u V(P). By Lemma 7, we have |S| ≥ 4n – 8 or |V(P)| ≥ 4n – 9 for n ≥ 5. So we consider the following two subcases.

Case 2.1. |S| ≥ 4n – 8. Let C be a cycle in P. Since for each vertex u V(F), and V (LTQ_n) ≥ 4, the cycle C of length is not less than 4. Because V(C) Ì V(P) Ì F₁ D F₂, either |F₁ – F₂| ≥ 2 or |F₂ – F₁| ≥ 2. Thereby, either |F₁| = |S| + |F₁ – F₂| ≥ 4n – 6 or |F₂| = |S| + |F₁ – F₂| ≥ 4n – 6.

Case 2.2. |V(P)| ≥ 4n – 9. Since |V(P)| ≥ 4n – 9 and V (P) Ì F₁ D F₂, either |F₁ – F₂| ≥ 2n – 4 or |F₂ – F₁| ≥ 2n – 4. And since there is no isolated vertex in LTQ_n (both F₁ and F₂ are conditional faulty set) and LTQ_n – S is disconnected, |S| ≥ 2n – 2 by lemma 3. Thereby, either|F₁| = |S| + | F₁ – F₂| ≥ 4n – 6 or |F₂| = |S| + |F₂ – F₁| ≥ 4n – 6.

Consequently, the theorem holds. ■

The theorem 1 shows that the conditional diagnosability of LTQ_n is not less than 4n – 7 for n ≥ 5. In the following we will show that the conditional diagnosability of LTQ_n is not more than 4n – 7 for n ≥ 5.

Theorem 2. £ 4n – 7 for n ≥ 3.

Proof: (See Figure 2) Let C = (u₁, u₂, u₃, u₄) be a cycle of length 4 in LTQ_n. u₁, u₂, u₃, u₄ are the four consecutively vertices in the cycle C. Let F₁ = {u₁, u₂} and F₂ ={u₃, u₄}. It is easy to verify that F₁and F₂ are two indistinguishable conditional faulty

set. It is easy to see that there exists no triangle in LTQ_n and any two distinct vertices in LTQ_n have at most two common neighbors. Thus we have |F₁F₂| = = 4n – 8 and | F₁ – F₂| = |F₂ – F₁|. So |F₁| = |F₂| = 4n – 6. Hence, LTQ_n is not conditionally (4n – 6) diagnosable. We are done. ■

By Theorems 1 and 2, the following corollary holds.

Corollary 1. = 4n – 7 for n ≥ 5.

4. Conclusions

Since the probability that any faulty set contains all the neighbors of some processor is very small, conditional diagnosability, requiring that each processor of a system is incident with at least one fault-free processor, can better measure the diagnosability of interconnection. In this paper, the main contribution is the determination of the conditional diagnosability of the locally twisted cubes. We obtain that the conditional diagnosability of a locally twisted cube under the PMC model is = 4n – 7 for n ≥ 5.

5. References

[1]       G. M. F. P. Preparata and R. T. Chien, “On the Connection Assignment Problem of Diagnosable Systems,” IEEE Transactions on Electronic Computers, vol. EC-16, No. 6, December 1967, pp. 848-854. doi:10.1109/PGEC.1967.264748

[2]       M. M. J. Maeng, “A Comparison Connection Assignment for Self-Diagnosis of Multiprocessors Systems,” Proceedings of the 11th International Symposium on FaultTolerant Computing, Portland, 1981, pp. 173-175.

[3]       F. G. F. Barsi and P. Maestrini, “A Theory of Diagnosability of Digital Systems,” IEEE Transactions on Computers, Vol. C-25, No. 6, June 1976, pp. 585-593. doi:10.1109/TC.1976.1674658

[4]       R. Ahlswede and H. Aydinian, “On Diagnosability of Large Multiprocessor Networks,” Discrete Applied Mathematics, Vol. 156, No. 18, 2008, pp. 3464-3474. doi:10.1016/j.dam.2008.02.001

[5]       D. Wang, “Diagnosability of Enhanced Hypercubes,” IEEE Transactions on Computers, vol. 43, no. 9, 1994, pp. 1054- 1061. doi:10.1109/12.312114

[6]       J. Fan, “Diagnosability of the Mobius Cubes,” IEEE Transactions on Parallel and Distributed Systems, vol. 9, no. 9, 1998, pp. 923-928. doi:10.1109/71.722224

[7]       P.-L. Lai, J. Tan, C.-P. Chang and L.-H. Hsu, “Conditional Diagnosability Measures for Large Multiprocessor Systems,” IEEE Transactions on Computers, Vol. 54, No. 2, 2005, pp. 165-175. doi:10.1109/TC.2005.19

[8]       S. Hsieh and C. Lee, “Diagnosability of Two-Matching Composition Networks under the MM* Model,” IEEE Transactions on Dependable and Secure Computing, Vol. 8, No. 2, 2009, pp. 246-255.

[9]       Q. Zhu, S.-Y. Liu and M. Xu, “On Conditional Diagnosability of the Folded Hypercubes,” Information Sciences, Vol. 178, No. 4, 2008, pp. 1069-1077. doi:10.1016/j.ins.2007.09.005

[10]    M. Xu, K. Thulasiraman and X.-D. Hu, “Conditional Diagnosability of Matching Composition Networks under the Pmc Model,” IEEE Transactions on Circuits and Systems II: Express Briefs, Vol. 56, No. 11, 2009, pp. 875- 879. doi:10.1109/TCSII.2009.2030361

[11]    Q. Zhu, “On Conditional Diagnosability and Reliability of the bc Networks,” The Journal of Supercomputing, Vol. 45, No. 2, 2008, pp. 173-184. doi:10.1007/s11227-007-0167-8

[12]    S.-M. Zhou, “The Conditional Diagnosability of Locally Twisted Cubes,” Proceedings of the 4th International Conference on Computer Science and Education, 2009, pp. 221-226.

[13]    J. A. Bondy and U. S. R. Murty, “Graph Theory with Applications,” North Holland, New York, 1976.

[14]    X.-F. Yang, D. J. Evans and G. M. Megson, “The Locally Twisted Cubes,” International Journal of Computer Mathematics, Vol. 82, No. 4, April 2005, pp. 401-413. doi:10.1080/0020716042000301752

[15]    G. M. A. T. Dahbura, “An O(n^2.5) Fault Identification Algorithm for Diagnosable Systems,” IEEE Transactions on Computers, Vol. C-33, No. 6, 1984, pp. 486-492. doi:10.1109/TC.1984.1676472

[16]    A. T. Dahbura and G. M. Masson, “An O(n^2.5) Fault Identification Algorithm for Diagnosable Systems,” IEEE Transactions on Computers, Vol. 33, No. 6, 1984, pp. 486-492. doi:10.1109/TC.1984.1676472

[17]    J.-X. Fan, S.-K. Zhang, et al., “The Restricted Connectivity of Locally Twisted Cubes,” 2009 10th International Symposium on Pervasive Systems, Algorithms, and Networks (ISPAN), Kaohsiung, 14-16 December 2009, pp. 574-578. doi:10.1109/I-SPAN.2009.48

[18]    J. Fan and X. Lin, “The t/k-Diagnosability of the BC Graphs,” IEEE Transactions on Computers, Vol. 54, No. 2, 2005, pp. 176-184. doi:10.1109/TC.2005.33

[19]    X.-F. Yang, J.-Q. Cao, G. M. Megson and J. Luo, “Minimum Neighborhood in a Generalized Cube,” Information Processing Letters, Vol. 97, 2006, pp. 88-93.

NOTES

^*The paper supported by the National Natural Science Foundation of China (No.61073196 )and Natural Science Research Foundation of Shanxi Province, China (No. 2011JM8026).