Printer Friendly

The Strong Local Diagnosability of a Hypercube Network with Missing Edges.

1. Introduction

In a multiprocessor system incorporating a large number of processors (nodes), some processors may fail. In other words, there may exist faulty processors in such a system. Faulty processors in a multiprocessor system will affect the reliability of the system. Hence, in the system design, the problem of self-diagnosis should be considered. Whenever a faulty node is identified by the system, it should be repaired or replaced with an additional one. The process of identifying faulty processors is referred to as fault diagnosis, which has been widely studied in [1-9]. The diagnosability, a key measurement of self-diagnosis capacity, of a system is the upper limit on the number of faulty processors that a system is certain to identify.

The hypercube network structure [10] is a popular topology in modeling a multiprocessor system. An n-dimensional hypercube network, denoted as [Q.sub.n], consists of [2.sup.n] nodes and [n2.sup.n-1] edges. A binary n-bit string, e.g., [x.sub.1][x.sub.2], ..., [x.sub.n], can be employed to denote the address of a node x in [Q.sub.n]. If the address of node u and the address of node v are different in exactly one bit position, then they are connected by a link, and vice versa. For two nodes u and v in [Q.sub.n], if x and y are connected by a link and their addresses differ in the ith position, then this edge is called the ith-dimensional edge. [Q.sub.n] can be decomposed in two (n-1)-dimensional hypercube networks [Q.sup.0.sub.n-1] and [Q.sup.1.sub.n-1] along the ith-dimensional edges. Let [v.sub.0] [member of] V([Q.sup.0.sub.n-1]). Then there must be another node [v.sub.1] [member of] V([Q.sup.1.sub.n-1]) satisfying ([v.sub.0], [v.sub.1]) [member of] E([Q.sub.n]). We call this edge the crossing edge between [Q.sup.0.sub.n-1] and [Q.sup.1.sub.t-1].

In system-level fault diagnosis, two models that are typically used as fault diagnosis models are the PMC model [11] and the comparison model [12]. The fault diagnosis model in this paper is the PMC model. "PMC" stands for Preparata, Metze, and Chien, as this model was first proposed by Preparata et al. in [11]. In [11], Preparata et al. put forward the concept of a one-step t-diagnosable system and of a sequentially i-diagnosable system. Since then, results corresponding to the PMC model have been widely reported (see [9, 11, 13-19]). In the PMC model, when we consider the diagnosability of a system S with missing edges, if all neighbors of some node are faulty, then it is impossible to judge whether or not the node is fault-free. In other words, in the PMC model, the diagnosability of a system S with missing edges depends on the upper limit of the minimum degree of S. In practice, the probability that all neighbors of a node are synchronously faulty is very low. For example, consider an n-dimensional hypercube network [Q.sub.n]; the number of node subsets such that its cardinality is n is [mathematical expression not reproducible]. However, the number of node subsets such that its size is n and it incorporates all neighbors of some node is at most [2.sup.n]. The ratio [mathematical expression not reproducible] implies that the probability that there exists some node such that its neighbors are all faulty is very low. For this reason, Lai et al. [14] proposed a concept called a strongly t-diagnosable system (STDS). Lai et al. [14] claimed that a STDS is a (t + 1)-diagnosable system provided that the system does not have a node such that its neighbors are all faulty simultaneously, the probability of which is very low. In other words, a STDS is nearly a (t + 1 -diagnosable system. In a certain sense, the SD of a system is more precise than its traditional diagnosability. Much research on SD has been carried out (see [2-4, 6, 9, 14]).

It is worth mentioning that in analyzing the diagnosability of a system, if one considers only the global situation and ignores some local information, it is possible that the diagnosability obtained is not the largest. For example, let S denote the integrating system produced by [Q.sub.r] and [Q.sub.s], where s > > r. The diagnosability of S may be less than r. However, the system may diagnose all faulty processors even if their number is greater than r and less than s. Thus, it is possible that if some local details of a system are ignored, then the amount of details obtained will be less than that in the practical case. In practice, the local status of a system is also an indicative of the entire system. Hence, when we consider the problem of the diagnosability of a system, it is necessary to study the local properties of the system. In 2007, Hsu and Tan [20] proposed a novel diagnosability, called local diagnosability, in order to study the problem of fault diagnosis of a system under the PMC model. Later, in 2009, Chiang and Tan [13] extended the results in [20] from the PMC model to the comparison model. Now, we are led to the following question: is it possible to present a concept that describes the local status with respect to the SD of a system? This article presents a concept called SLD, which describes nodes' local SD status of a system. A sufficient and necessary condition, which tests the SLD of a node and its relationship with the SD of a system, is discussed in this article. Based on this sufficient and necessary condition, we conclude that the SD of a system can be determined by computing the SLD of each node of the system. Then, it is obtained that the SLD of a node of [Q.sub.n] is n, where n [greater than or equal to] 4. Moreover, we discuss the SLD of a given node of an incomplete hypercube network [21].

The remainder of this paper is as follows: after introducing some necessary preliminaries and the terminology used in this paper, in Section 3, we present the concept of SLD and an important theorem for checking the SLD of a given node in a system. In Section 4, the SLD of a node of [Q.sub.n] is studied. Finally, in Section 5, we discuss the conclusions of our paper.

2. Preliminaries

A system is usually described by a graph H(V, E), where E represents all communication edges between processors and V represents the set of all processors. Throughout this paper, we will use the following terms interchangeably: graph, multiprocessor system and interconnection system. Moreover, we will use node, vertex, and processor interchangeably. The definition of a graph follows that given in [22]. For a node u in H(V, E), a node v is said to be its neighbor if (u, v) [member of] E. Moreover, let [N.sub.H](z) = {y | (y, z) [member of] E} (N(z), in no confusion) represent the set of all neighbors of z. The degree of a node z in H, denoted by [deg.sub.H](z) (deg (z), no confusion), is the cardinality of N(z), i.e., deg (z) = [absolute value of N(z)]. If the degree of each node in H is k, then H is said to be k-regular. For a disconnected graph H, a connected component of H refers to a maximal connected subgraph of H. If a connected component does not have any edges, it is said to be trivial; otherwise, it is nontrivial. Given a node subset X, let H-X represent a subgraph created by deleting X from H. Similarly, given an edge subset E', let H-E' represent a graph obtained by removing E' from H. The connectivity of H, denoted by k(H), is the cardinality of the minimum node set X (X [subset] V) such that H-X is disconnected. If k(H) [greater than or equal to] r, then H is said to be r-connected. For a graph H(V, E), we use V(H) (E(H), respectively) to denote the node set of H (the edge set of H, respectively).

In the PMC model, if (x, y) [member of] E, then x and y can be used to test each other. We use the order pair (x, y) to represent that x tests y. In this situation, x is the tester, and y is the tested node. The PMC model assumes that if y is diagnosed to be faulty (fault-free) by x, then the outcome of x testing y is 1 (0), denoted by [sigma](x, y) = 1 ([sigma](x, y) = 0). We use [sigma] = {[sigma](x, y) | (x, y) [member of] E} to denote a syndrome. The collection of all faulty nodes in H is called a faulty set. It is possible that any subset of V is a faulty set. The fault diagnosis of a system refers to the process of identifying all faulty nodes in the system. In a system H, the cardinality of a maximum faulty node set that can be identified by H is called its diagnosability, denoted as t(H). Given a syndrome [sigma], a set S [subset or equal to] V(H) is called consistent with [sigma] if the following condition is true: if [for all]x [member of] V(H)-S and (x, y) [member of] E, then [sigma](x, y) = 1 if and only if y [member of] S.

We use [sigma](S) to denote the set of syndromes produced by faulty node set S. Two subsets X, Y [subset or equal to] V(H) are called distinguishable if [sigma](X) [intersection] [sigma](Y) = [empty set]. If X and Y are distinguishable, then (X, Y) is said to be a distinguishable pair; otherwise, (X, Y) is said to be an indistinguishable pair. Let X[DELTA]Y = (X-Y) [union] (Y-X). In addition, we need some previous results concerning the t-diagnosable system. Throughout this paper, the fault diagnosis model refers to the PMC model.

Lemma 1 (see [23]). A system H(V, E) is t-diagnosable if and only if for two arbitrary different subsets X, Y c V satisfying [absolute value of X] [less than or equal to] t, [absolute value of Y] [less than or equal to] t, (X, Y) is always a distinguishable pair.

Lemma 2 (see [23]). In a system H(V, E), suppose that X, Y [subset] V with [absolute value of X] [less than or equal to] t, [absolute value of Y] [less than or equal to] t are two different subsets. Then (X, Y) is a distinguishable pair if and only if H has at least an edge (x, y) [member of] E such that x [member of] V-X-Y and y [member of] X[DELTA]Y (Figure 1).

The following lemmas are related to the concept of node diagnosability:

Lemma 3 (see [20]). Suppose that H(V, E) is a system, z [member of] V. H is locally t-diagnosable at z if and only if for each subset X [subset] V with [absolute value of X] = l, l [member of] {0, 1, ..., 1}, and z [not member of] X, the number of nodes in the connected component containing z in H-X is greater than 2(t-l).

Lemma 4 (see [20]). Suppose that H(V, E) is a graph, v [member of] V with deg (v) = k. Then, the locally diagnosability (LD) of node v does not exceed k.

Lemma 5 (see [20]). In a system H(V, E), suppose that z [member of] V. Then the system H(V, E) is t-diagnosable at node z [member of] V(G) if and only if for two arbitrary different subsets X, Y [subset] V(H) satisfying [absolute value of X] [less than or equal to] t, [absolute value of Y] [less than or equal to] t and z [member of] X[DELTA]Y, H has at least an edge (x, y) [member of] E such that x [member of] V-X-Y and y [member of] X[DELTA]Y.

Lemma 6 (see [20]). A t-diagnosable system H is locally t-diagnosable at each node. Conversely, if H is locally t-diagnosable at each node, then H is t-diagnosable.

By Lemma 1 and Lemma 5, we conclude that a t-diagnosable system must be t-diagnosable at each node, and vice versa.

Definition 1. A system is triangle-free if it does not incorporate a triangle.

Remark 1. Among the regular interconnection networks, there are many famous networks that are triangle-free, for example, hypercube-like networks [18], star networks [7], and the exchanged hypercube network [24].

The following definition of a strongly t-diagnosable system follows [14].

Definition 2. A t-diagnosable system, denoted by H(V, E), is called a strong t-diagnosable system if the following condition is true.

For any two different subsets X, Y [subset] V with [absolute value of X] [less than or equal to] t + 1 and [absolute value of Y] [less than or equal to] t + 1, if (X, Y) is an indistinguishable pair, then H has at least a node x such that N(x) [subset or equal to] X [intersection] Y.

The strong diagnosability (SD) of a system is the maximum number value of t such that the system is a strong t-diagnosable system.

3. The Strong Local Diagnosability

First, let us look back at some conclusions regarding diagnosability. Reference [20] proposed a new concept, called node diagnosability, that describes the local status with respect to system diagnosability. By Lemma 6, to obtain the system diagnosability, we need only to compute the node diagnosability of each node of the system, which is a novel way to study the system diagnosability. By Definition 2, we have that a STDS must be a t-diagnosable system but may not be a (t + 1)-diagnosable system [13]. Since the probability that all neighbors of some node are faulty simultaneously is rather small, a STDS is almost t + 1-diagnosable. Motivated by this strategy, we propose a new concept called the SLD at a given node in a system. This new concept combines the characteristics of node diagnosability and SD. For a system H(V, E), x [member of] V, we use t(H) ([t.sub.l](x); [t.sub.sl]H(x)) to denote the diagnosability of H(V, E) (the LD at node x in H(V, E); the SLD at node x in H(V, E)).

Definition 3. Let H(V, E) be the diagnostic graph of a system H and x [member of] V. H is called strong locally t-diagnosable at node x if it is locally t-diagnosable at node x and the following condition is true.

For any two different subsets X, Y [subset] V with [absolute value of X] [less than or equal to] t + 1, [absolute value of Y] [less than or equal to] t + 1 and x [member of] X[DELTA]Y, if (X, Y) is an indistinguishable pair, then N(x) [subset or equal to] S X [intersection] Y.

A system H is said to be strong locally t-diagnosable if for each node x in H, H is strong locally t-diagnosable at node x.

Proposition 1. Suppose that H(V, E) is a graph, y [member of] V with deg (y) = k. The SLD of node y in H(V, E) does not exceed k.

Proof 1. By Lemma 4 and Definition 3, the proof can be easily obtained.

In the following, we propose two propositions for describing the relationship between a strong locally t-diagnosable system and a strongly t-diagnosable system:

Proposition 2. If H(V, E) is strong locally t-diagnosable, then H(V, E) is strongly t-diagnosable.

Proof 2. Suppose that H(V, E) is not strongly t-diagnosable. From Definition 1, it is obtained that there is an indistinguishable pair (X, Y) with X, Y [subset] V, X [not equal to] Y, [absolute value of X] [less than or equal to] t + 1, and [absolute value of Y] [less than or equal to] t + 1 such that for any node x [member of] V, N(x) [not subset] X [intersection] Y. Since X [not equal to] Y, there exists a node y such that y [member of] X[DELTA]Y and N(y) [not subset] X [intersection] Y. Hence, H is not strong locally t-diagnosable at node y, a contradiction to the postulation that H is strong locally t-diagnosable. This completes the proof.

The above proposition proposes a sufficient but unnecessary condition to test if the system S is strongly t-diagnosable. Next, a necessary and sufficient condition for testing the strong t-diagnosability of a triangle-free system is presented.

Proposition 3. Let H(V, E) be a triangle-free system and t [greater than or equal to] 3 be an integer. If H is strongly t-diagnosable, then H is strong locally t-diagnosable, and vice versa.

Proof 3. By the proof of Proposition 2, the sufficiency holds.

Necessity 1. Let H be a strongly t-diagnosable system; then, H is t-diagnosable. Let x [member of] V .By Lemma 6, we have that H is locally t-diagnosable at vertex x. Next, by Definition 3, we need to prove only that for any two different subsets X, Y [subset] V with [absolute value of X] [less than or equal to] t + 1 and [absolute value of Y] [less than or equal to] t + 1, if (X, Y) is an indistinguishable pair, then H has at least a node x [member of] X[DELTA]Y and N(x) [subset or equal to] X [intersection] Y. In contrast, assuming that N(x) [not subset] X [intersection] Y, we derive a contradiction. By Definition 2, there is at least one node y [member of] V such that N(y) [subset or equal to] N(X) [intersection] N(Y). By Lemma 4, we have that [absolute value of X [intersection] Y] [greater than or equal to] [absolute value of N(y)] [greater than or equal to] t. Note that X [not equal to] Y, [absolute value of X] [less than or equal to] t + 1, and [absolute value of Y] [less than or equal to] t + 1; therefore, [absolute value of X [intersection] Y] [less than or equal to] t. Thus, [absolute value of X [intersection] Y] = [absolute value of N(y)] = t. On the other hand, x [member of] X[DELTA]Y implies that x [member of] X-Y or x [member of] Y-X. Here, we need to consider only the situation where x [member of] X-Y, as the proof of the situation in which x [member of] Y-X can be similarly obtained. In the rest of this proof, four situations are considered according to the subjections of node y: (1) y [member of] X-Y, (2) y [member of] Y-X, (3) y [member of] X [intersection] Y, and (4) y [member of] V-(X [union] Y).

Case 1 (y [member of] X-Y). Since [absolute value of X-Y] [less than or equal to] 1 and X [not equal to] Y, x = y, which is a contradiction.

Case 2 (y [member of] Y-X). It is clear that Y-X = {y}, X-Y = {x}. (X, Y) is an indistinguishable pair, implying that N(x) [intersection] (V-X [union] Y) = [phi]. Moreover, by N(x) [not subset or equal to] X [intersection] Y, we have that y [member of] N(x). This is a contradiction to N(y) S [subset or equal to] X [intersection] Y.

Case 3 (y [member of] X [intersection] Y). Since [absolute value of X [intersection] Y] = [absolute value of N(y)] = t and N(y) [subset or equal to] X [intersection] Y, N(y) = X [intersection] Y, which is a contradiction.

Case 4 (y [member of] V-(X [union] Y)). By the hypothesis, we have that X-Y = {x} and [absolute value of Y-X] [less than or equal to] 1. We first discuss the situation where [absolute value of Y-X] = 1. Suppose that Y-X = {z}. By the proof of Case 2, we have that x is adjacent to z and that there is no edge between z and any node in V-(X [union] Y). N(x) [intersection] (V-X [intersection] Y) = [phi] (as (X, Y) is an indistinguishable pair) and [absolute value of N(x)] [greater than or equal to] t (Lemma 4), we have that [absolute value of N(x) [union] (X [union] Y)] [greater than or equal to] t-1. Since H is a triangle-free graph, [absolute value of N(z) [intersection] (X [intersection] Y)] [less than or equal to] 1. Thus, the degree of z is no greater than 2, a contradiction to deg (z) [greater than or equal to] t [greater than or equal to] 3 (Lemma 4). Second, we consider the situation where [absolute value of Y-X] = 0. Since there is no edge between x and any node in V-(X [union] Y), N(x) S [subset or equal to] X [union] Y; thus, N(x) [subset or equal to] X, and therefore, N(x) [union] {x} [subset] X. On the other hand, since N(x) [greater than or equal to] t, X = {x} [union] N(x), and hence, Y = N(x), which is a contradiction. This completes the proof.

Proposition 2 describes the relationship between SLD and SD for a triangle-free graph. The following theorem follows Proposition 2.

Theorem 1. In a triangle-free network system H(V, E), the strong diagnosability of H is equal to min {the SLD at node r | r[member of] V}.

The following sufficient and necessary condition can be applied.

Theorem 2. In a graph H(V, E), x [member of] V. Thus, H(V, E) is strong locally t-diagnosable at node x if and only if, for any S [subset] V, [absolute value of S] = l, l [member of]{0, 1, ..., t}, and x [not member of] S, the following conditions hold:

Condition 1 If l [not equal to] t, then the number of nodes of the connected component containing x in H-S exceeds 2(t + 1-l).

Condition 2 If l = t, then either (a) the number of nodes of the connected component containing x in H-S exceeds 2 or (b) N(x) [subset or equal to] S.

Proof 4 (sufficiency). Let C denote the connected component containing x in H-S. By Condition 1, for l [not equal to] t, we have that 2(t-l) + 1 < 2 (t + 1-l) + 1 [less than or equal to] [absolute value of V(C)]. According to Lemma 3, H is locally t-diagnosable at node x. Next, we need to prove that for any two different subsets X, Y [subset] V with [absolute value of X] [less than or equal to] t + 1, [absolute value of Y] [less than or equal to] t + 1 and x [member of] X[DELTA]Y, if (X, Y) is an indistinguishable pair, then N(x) [subset or equal to] X [intersection] Y. Suppose that there exist two different subsets X, Y [subset] V with [absolute value of X] [less than or equal to] t + 1, [absolute value of Y] [less than or equal to] t + 1 and x [member of] X[DELTA]Y such that (X, Y) is an indistinguishable pair and N(x) [not subset or equal to] X [intersection] Y .Let S' = X [intersection] Y; then, [absolute value of S'] = l [less than or equal to] t. If l [not equal to] t, by Condition 1, the number of nodes of the connected component containing x in H-S' is greater than 2(t + 1-l). Moreover, the number of nodes of the connected component containing x in H-S' is greater than [absolute value of X[DELTA]Y], which implies that H has two nodes y [member of] V-X [union] Y and z [member of] X[DELTA]Y such that (y, z) [member of] E.

Hence, (X, Y) is a distinguishable pair, which is a contradiction. Thus, [absolute value of S'] = l = t, which implies that [absolute value of X[DELTA]Y] [less than or equal to] 2. By Condition 2, we have that the number of nodes of the connected component containing x in H-S' exceeds 2. Hence, H has two nodes y [member of] V-X [union] Y and z [member of] X[DELTA]Y such that (y, z) [member of] E. Hence, (X, Y) is a distinguishable pair, which is a contradiction.

Next, we consider the situation l = t. From last paragraph, we have that H is locally t-diagnosable at node x. By Definition 3, we only need to prove that for any two different subsets X, Y [subset] V with [absolute value of X] [less than or equal to] t + 1, [absolute value of Y] [less than or equal to] t + 1 and x [member of] X[DELTA]Y, if (X, Y) is an indistinguishable pair, then N(x) [subset or equal to] X [intersection] Y. To the contrary, assume that there exist two different subsets X, Y [subset] V with [absolute value of X] [less than or equal to] t + 1, [absolute value of Y] [less than or equal to] t + 1, x [member of] X[DELTA]Y and (X, Y) is an indistinguishable pair, but N(x) [not subset or equal to] X [intersection] Y. Let S' = X [intersection] Y and [absolute value of S'] = r, then 0 [less than or equal to] r [less than or equal to] t, and then we have that [absolute value of X[DELTA]Y] [less than or equal to] 2(t + 1-r). Moreover, by Condition 1, we have that r = t, which implies that [absolute value of X[DELTA]Y] [less than or equal to] 2. Since (X, Y) is an indistinguishable pair, there is no edge from V-(X [union] Y) to X[DELTA]Y. So, the number of nodes of the connected component containing x is no more than [absolute value of X[DELTA]Y] 4 2. Moreover, N(x) [subset or equal to] S' = X [intersection] Y, a contradiction.

Necessity 2. We consider Condition 1 first. Suppose that for some l [member of]{0, 1, ..., t-1}, H-S has a connected component containing x, e.g., C, such that [absolute value of V(C)] [less than or equal to] 2(t + 1-1). Let V(C) be decomposed in two subsets as follows: [R.sub.1] [intersection] [R.sub.2] = [empty set] and [R.sub.1] [union] [R.sub.2] = V(C), with [absolute value of [R.sub.1]] [less than or equal to] (t + 1-l) and [absolute value of [R.sub.2]] [less than or equal to] (t + 1-l). Let X = [R.sub.1] [union] S and Y = [R.sub.2] [union] S. It is clear that [absolute value of X] [less than or equal to] t + 1, [absolute value of Y] [less than or equal to] t + 1 and x [member of] X[DELTA]Y. Since C is a connected component of H-S, H does not have an edge (y, z) [member of] E such that y [member of] X[DELTA]Y and z [member of] V-(X [union] Y). By Lemma 2, (X, Y) is an indistinguishable pair. Since H is strong locally t-diagnosable at node x, N(x) [subset or equal to] S. Hence, [absolute value of N(x)] [less than or equal to] [absolute value of S] [less than or equal to] l [less than or equal to] t-1. On the other hand, the assumption that H is strong locally t-diagnosable at node x implies that H is t-diagnosable at node x. By Lemma 4, we have that [absolute value of N(x)] [greater than or equal to] t, which is a contradiction. Hence, Condition 1 is necessary.

Now, let us consider Condition 2. Suppose that [absolute value of S] = l = t. Let L denote the connected component containing x in H-S. If the number of nodes in L is less than or equal to 2, then V(L) can be decomposed in two subsets [R.sub.1] and [R.sub.2] satisfying the following conditions: [R.sub.1] [intersection] [R.sub.2] = [empty set] and [R.sub.1] [union] [R.sub.2] = V(L), with [absolute value of [R.sub.1]] [less than or equal to] 1 and [absolute value of [R.sub.2]] [less than or equal to] 1. Let X = [R.sub.1] [union] S and Y = [R.sub.2] [union] S. Then, [absolute value of X] [less than or equal to] t + 1, [absolute value of Y] [less than or equal to] t + 1, and x [member of] X[DELTA]Y. By the assumption that H(V, E) is strong locally t-diagnosable at node x, we have that H(V, E) is locally t-diagnosable at node x. Moreover, we have that (X, Y) is an indistinguishable pair. By Definition 3, we conclude that N(x) [subset or equal to] X [intersection] Y = S. This completes the proof of necessity.

Corollary 1. Suppose that H'(V', E') is a subgraph of H(V, E), y [member of] V'. If H'(V', E') is strong locally t-diagnosable at y and [N.sub.H](y) [subset or equal to] V', then H(V, E) is strong locally t-diagnosable at y.

Proof 5. For any S [subset] V, [absolute value of S] = l, l [member of] {0, 1, ..., t}, and x [not member of] S. We will prove that the two conditions in Theorem 2 hold. Let S' = S [intersection] V', l' = [absolute value of S']. Consider the following cases:

Case 5 (l [not equal to] t). Note that l' [not equal to] t. Since H' (V', E') is strong locally t-diagnosable at y, the number of nodes of the connected component containing y in H'-S' exceeds 2(t + 1-l'), which implies the number of nodes of the connected component containingy in H-S exceeds 2(t + 1-l'). Moreover, the number of nodes of the connected component containing y in H-S exceeds 2(t + 1-l). So, Condition 1 of Theorem 2 holds.

Case 6 (l = t).

Case 7 (l' [not equal to] t). An argument being similar to Case 5 can be used to obtain the following result: the number of nodes of the connected component containing y in H'-S' exceeds 2 (t + 1-l'), which implies that the number of nodes of the connected component containing y in H-S exceeds 2. So, Condition 2 of Theorem 2 holds.

Case 8 (l' [not equal to] t). Then S' = S. Since H' (V', E') is strong locally t-diagnosable at y and [N.sub.H](y) [subset or equal to] V', then either (a) the number of nodes of the connected component containing y in H'-S' exceeds 2, which implies the number of nodes of the connected component containing y in H-S exceeds 2, or (b) [N.sub.H'](y) [subset or equal to] S', which implies [N.sub.H](y) [subset or equal to] S. So, Condition 2 of Theorem 2 holds.

Next, we present the type I structure, which is used to verify the SLD of a given node.

Definition 4. Suppose that H(V, E) denotes a diagnostic graph of a system and that x is a node in V. The type I structure of the node x can be decomposed in three node sets ([L.sub.1], [L.sub.2], and [L.sub.3]) and two edge sets ([E.sub.1], [E.sub.2]), as shown in Figure 2. These sets are defined as follows: [L.sub.1] = {x}, [L.sub.2] = {y | (y, x) [member of] E}, and [L.sub.3] = {z | (z, y) [member of] E, y [member of] [L.sub.2]}. [E.sub.1] = (x, y) | x [member of] [L.sub.1], y [member of] [L.sub.2]}, and [E.sub.2] = {(y, z) | y [member of] [L.sub.2], z [member of] [L.sub.3]}. Let [N.sub.n] ([N.sub.e]) represent the number of nodes (edges) in the type I structure.

4. The Hypercube Network and Incomplete Hypercube

Regular topology structures are usually used to imitate multiprocessor systems. There is no doubt that the hypercube structure is one of the most important regular topology structures. In the following, we will discuss the problem of the SLD of a hypercube network.

Theorem 3. [Q.sub.n] is strong locally n-diagnosable at each node, where n [greater than or equal to] 4.

Proof 6. Let v [member of] V([Q.sub.n]) be an arbitrary node. For each S [subset] V ([Q.sub.n]), [absolute value of S] = l, l [member of] {0, 1, ..., n}, and v [not member of] S, we show that the two conditions of Theorem 2 are both true.

Case 9 (l [not equal to] n). Noting that the connectivity of [Q.sub.n] is n, we have that [Q.sub.n]-S is connected. Let C denote this unique connected component in [Q.sub.n]-S; then, v [member of] V(C). Hence, [absolute value of V(C)] = [2.sup.n]-l [greater than or equal to] 2(t + 1-l) + 1 (n [greater than or equal to] 4), which implies that Condition 1 of Theorem 2 holds.

Case 10 (l = n). Consider the type I structure of node v in [Q.sub.n]. If S [subset] [L.sub.2], then N(v) [subset or equal to] S, which implies that Condition 2 of Theorem 2 is true. If [not subset or equal to] [L.sub.2], then there are two nodes u, w satisfying u [member of] [L.sub.2], w [member of] [L.sub.3], and (v, u) [member of] [E.sub.1], (u, w) [member of] [E.sub.2]. Hence, [Q.sub.n]-S has a connected component, which incorporates v and has 3 or more nodes. This completes the proof of Theorem 3.

According to Theorem 3, the SLD of every node of [Q.sub.n] is the same as its degree, with n [greater than or equal to] 4. It is natural to consider the following question: is the result still true for an incomplete hypercube network? In the following, we discuss this problem. We use E' [subset] E to denote an edge subset and [Q'.sub.n] to denote an incomplete hypercube network of n dimensions created by removing E' from the hypercube network [Q.sub.n]. In the following, we show that the SLD of every node is the same as its RD in [Q'.sub.n], even if the cardinality of E' can reach (n-3). We now give an example to explain that the result is not true if the cardinality of E' is (n-2). In Figure 3, deg (x) = n. Let E' = {(x, u) [member of] E | u [member of] V}-{(x, y)}-{(x, v)}, where u and v are two neighbors of x; then, [absolute value of E'] = n-2. Let [mathematical expression not reproducible]; then, [absolute value of X] = [absolute value of Y] = n + 1, v [member of] X[DELTA]Y. By Lemma 2, (X, Y) is an indistinguishable pair, and N(v) [subset] X [intersection] Y. Hence, the SLD of node v differs from its RD in [Q'.sub.n].

Theorem 4. Let E' [subset] E([Q.sub.n]) be an edge subset with 0 [less than or equal to] [absolute value of E'] [less than or equal to] n-3, where n [greater than or equal to] 4. Let [Q'.sub.n] denote the induced subgraph of E([Q.sub.n])-E'. Then, the SLD of every node of [Q'.sub.n] is exactly the same as its RD.

Proof 7. We prove this theorem by induction n. First, let us consider the situation where n = 4; in this case, [absolute value of E'] [less than or equal to] 1. For [absolute value of E'] = 0, based on Theorem 3, the result holds. Assume that [absolute value of E'] = 1. We consider the type I structure of node v in [Q.sub.4], as shown in Figure 4. It is clear that [absolute value of [L.sub.1]] + [absolute value of [L.sub.2]] + [absolute value of [L.sub.3]] = 1 + 4 + 6 = 11. If E' [subset] [E.sub.1], then the RD of v is 3. We can use a similar argument to that used in the proof of Theorem 3 to show that the SLD of node v is 3. If E' [subset] [E.sub.2], then the RD of v is 4. Let S [subset] V([Q'.sub.4]) and v [member of] S, with [absolute value of S] = l and 0 [less than or equal to] l [less than or equal to] 4. When l = 4 and N(v) [subset or equal to] S, Condition 2 of Theorem 2 holds. When l = 4 and N(v) [subset or equal to] S, consider the following cases.

Case 11 ([absolute value of N(v)-S] = 2). Then the number of nodes of the connected component containing v in [Q'.sub.4]-S is at least 3, Condition 2 of Theorem 2 holds.

Case 12 ([absolute value of N(v)-S] = 1. Then [absolute value of N(v) [internation] S] = 3. Let u [member of] N(v)-S, then N(u) [intersection] [L.sub.3] has at least 2 nodes, which implies [absolute value of N(u) [intersection] [L.sub.3]-S] [greater than or equal to] 1. So, the number of nodes of connected component containing v in [Q'.sub.4]-S is at least 3. In other words, Condition 2 of Theorem 2 holds.

Next, we show that when 0 [less than or equal to] l [less than or equal to] 3, [absolute value of V(C)] [greater than or equal to] 2(4 + 1-l) + 1 = 11-2l, where C is the connected component containing v in [Q'.sub.4]-S. From Figure 5, we conclude that the only case stopping the condition from being satisfied is that in which S = {[v.sub.2], [v.sub.3], [v.sub.4]} and E' = {([v.sub.1], [v.sub.11])}. However, based on the definition of a hypercube network, the connected component C contains other neighbors of [v.sub.1], e.g., [v.sub.12] and [v.sub.13], as well as their neighbors, which do not include [v.sub.1]. Hence, for connected component C, it is true that [absolute value of V(C)] [greater than or equal to] 5 when l = 3. In summary, for n = 4, the result is true.

Assume that when n [greater than or equal to] 5 for [Q'.sub.n-1], the result is true. Next, we prove that for n [greater than or equal to] 5, [Q'.sub.n] and 0 [less than or equal to] [absolute value of E'] [less than or equal to] (n-3), the result is still true. If [absolute value of E'] = 0, then the result holds. Now, we consider the situation where 1 [less than or equal to] [absolute value of E'] [less than or equal to] n-3. Decompose [Q.sub.n] in two (n-1) dimensional hypercube networks [Q.sup.0.sub.n-1] and [Q.sup.1.sub.n-1] along the ith-dimensional edges. Let [E'.sub.0] = E([Q.sup.0.sub.n-1]) [intersection] E', [E'.sub.1] = E([Q.sup.1.sub.n-1]) [intersection] E'. Let v be an arbitrary node. Without the loss of generality, let [mathematical expression not reproducible]. Suppose that (v, v') [member of] E([Q.sub.n]) is a crossing edge, namely, (v, v') [member of] E([Q.sub.n]) is one of the ith-dimensional edges, where v' [member of] V([Q.sup.1.sub.n-1]). Consider the following two cases:

Case 13 ((v, v') [member of] E'). Then, 0 [less than or equal to] [E'.sub.0]] [less than or equal to] (n-1)-3. By the inductive hypothesis, we have that [t.sub.sl]([Q.sup.1.sub.n-1]-[E'.sub.0])(v) = k. On the other hand, we have that [mathematical expression not reproducible]. According to Corollary 1 and Proposition 1, we have that [mathematical expression not reproducible]. Hence, [t.sub.sl]([Q.sub.n]-E') (v) = k, and thus the result is true.

Case 14 ((v, v') [not member of] E'). Then, [mathematical expression not reproducible]. By Proposition 1, we have that [t.sub.sl]([Q'.sub.n]-E')(v) [less than or equal to] k + 1. Now, we need to prove only that [Q.sub.n]-E is strong locally k + 1-diagnosable at node v. Let S [subset] V([Q.sub.n]-E'), with v [not member of] S, 0 [less than or equal to] [absolute value of S] = l [less than or equal to] k + 1, [S.sub.0] = S [intersection] V([Q.sup.0.sub.n-1]-[E'.sub.0]), and [S.sub.1] = S [intersection] V ([Q.sup.1.sub.n-1]-[E'.sub.1]). Next, we prove that the two conditions of Theorem 2 hold. For the sake of convenience, let C stand for the connected component containing v in ([Q.sub.n]-E')-S, [C.sub.0] denote the connected component containing v in ([Q.sup.0.sub.n-1]-[E'.sub.0])-[S.sub.0], and [C.sub.1] denote the connected component containing v' in ([Q.sup.1.sub.n-1]-[E'.sub.1])-[S.sub.1]; moreover, let [s.sub.i] = [absolute value of [S.sub.i]], i = 0, 1.

Case 15. First, we consider the condition that l [less than or equal to] k. We will prove that [absolute value of V(C)] [greater than or equal to] 2(k + 1 + 1-l) + 1. Consider the following cases:

Case 16 ([absolute value of [E'.sub.0]] = (n-3)).

Case 17 (v' [not member of] S). If [s.sub.1] [less than or equal to] n-2, then [absolute value of V([C.sub.1])] [greater than or equal to] [2.sup.n-1]-[s.sub.1]. Moreover, [mathematical expression not reproducible]. Moreover, [mathematical expression not reproducible].

Case 18 (v' [member of] S). It is obvious that [s.sub.0] [less than or equal to] k-1. Let (x, y) [member of] [E'.sub.0]; then, {x, y} has at least one node, e.g., x, which is not v. Let [[bar.S].sub.0] = [S.sub.0] [union] {x}; then, [absolute value of [[bar.S].sub.0]] [less than or equal to] [s.sub.0] + 1 [less than or equal to] k.

If [absolute value of [[bar.S].sub.0]] [less than or equal to] k-1, let [C.sub.0] denote the connected component containing v in ([Q.sup.0.sub.n-1]-([E'.sub.0]-{(x, y)})-[[bar.S].sub.0]). Since [Q.sup.0.sub.n-1]-([E.sub.0]-{(x, y)})-[[bar.S].sub.0] is the subgraph of [Q.sup.0.sub.n-1]-[E'.sub.0]-[S.sub.0], [absolute value of V([[bar.C].sub.0])] [greater than or equal to] [absolute value of V([[bar.C].sub.0])]. Note that [absolute value of [E'.sub.0]-{(x, y)}] = (n-1)-3; by inductive hypothesis and Theorem 2, we have that [absolute value of V([[bar.C].sub.0])] [less than or equal to] 2{k + 1-([s.sub.0] + 1)) + 1. In [Q.sup.0.sub.n-1]-[E'.sub.0]-[S.sub.0], we can choose two distinct nodes u and w such that either both u and w are neighbors of v or u is a neighbor of v and w is a neighbor of u. Suppose that (u, u') and (w, w') are two crossing edges in [Q.sub.n], where u', w' [member of] V([Q.sub.n-1]) and (u, u'), (w, w') [member of] E. If [s.sub.1] = 1, then V([[bar.C].sub.0]) [union] {u', w'} [subset] V(C), and then [mathematical expression not reproducible]. If [s.sub.1]1, then [s.sub.0] + 1 [less than or equal to] l-1, and then [mathematical expression not reproducible].

If [absolute value of [[bar.S].sub.0]] = k, then [s.sub.1] = 1, [s.sub.0] = k-1. Since [mathematical expression not reproducible], there must exist one neighbor of v, e.g., z, such that z [not equal to] x in [Q.sup.0.sub.n-1]-([E'.sub.0]-{(x, y)})-[[bar.S].sub.0]. Let (z, z') be a crossing edge in [Q.sub.n], where z' [member of] V([Q.sup.1.sub.n-1]. Let [C.sub.z'] denote the connected component containing z' in ([Q.sup.1.sub.n-1]-[E'.sup.1])-[S.sub.1]; then, [absolute value of V([C.sub.z'])] [greater than or equal to] [2.sup.n-1]-[s.sub.1]. Note that (z, z') [not member of] E'; we have that v, z, z' belong to a connected component of [Q.sub.n]-E', which implies that [mathematical expression not reproducible].

Case 19 ([absolute value of [E'.sub.0]] = 0.

If v' [member of] S, then [s.sub.0] [less than or equal to] k-1 [less than or equal to] n-2. Since the connectivity of [Q.sub.n-1] is n-1, [absolute value of V([C.sub.0])] [greater than or equal to] [2.sup.n-1]-[s.sub.0] [greater than or equal to] 2(k + 1 + 1-l) + 1. Hence, [absolute value of V(C)] [greater than or equal to] [absolute value of V([C.sub.0])] [greater than or equal to] 2(k + 1 + 1-l) + 1. If v' [not member of] S, then either [mathematical expression not reproducible]. Hence, [absolute value of V(C)] [greater than or equal to] 2(k + 1 + 1-l) + 1.

Case 20 (1 [less than or equal to] [absolute value of [E'.sub.0]] [less than or equal to] (n-1)-3). Next, we show that [absolute value of V(C)] [greater than or equal to] 2((k + 1 + 1-l) + 1. Since 0 [less than or equal to] [absolute value of [E'.sub.1]] [less than or equal to] (n-3)-1, the degree of any node in [Q.sup.1.sub.n-1]-[E'.sub.1] is at least 3. Therefore, v' has two neighbors, e.g., x and y, in [Q.sup.1.sub.n-1]-[E'.sub.1]. Consider the following cases:

Case 21 (0 [less than or equal to] l [less than or equal to] k-1). By inductive hypothesis and Theorem 2, we have that [absolute value of V([C.sub.0])] [greater than or equal to] 2(k + 1-[s.sup.0]) + 1. If [mathematical expression not reproducible].

Case 22 (l = k). Since 0 [less than or equal to] [absolute value of [E'.sub.1]] [less than or equal to] (n-3)-1, there exists another neighbor of v', e.g., [v'.sub.11], in [Q.sup.1.sub.n-1]-[E'.sub.1]. If S [subset or equal to] [Q.sup.0.sub.n-1]-[E'.sub.0], then [absolute value of V([C.sub.1])] [greater than or equal to] [2.sup.n-1], and then [absolute value of V(C)] [greater than or equal to] [absolute value of V([C.sub.1]) [union] {v}] [greater than or equal to] [2.sup.n-1] + 1 [greater than or equal to] 2((k + 1 + 1-l) + 1. If S [subset or equal to] [Q.sup.0.sub.n-1]-E', then [s.sub.0] [less than or equal to] k-1. Hence, by inductive hypothesis and Theorem 2, we have that [absolute value of V([C.sub.0])] [greater than or equal to] 2(k +1-([s.sub.0])) + 1 [greater than or equal to] 2((k + 1)-l) + 1.

Case 23. Next, we consider the condition that l = k +1. Suppose that [mathematical expression not reproducible]. Consider the following cases.

Case 24 (v' [not member of] S). Since[mathematical expression not reproducible], there is at least node y in [mathematical expression not reproducible] such that y [not member of] S. Hence, y, v, v' belong to a connected component in [Q.sub.n]-E'-S. Condition 2 of Theorem 2 is satisfied.

Case 25 (v' [member of] S). By [mathematical expression not reproducible], we conclude that there exists at least node in [mathematical expression not reproducible], e.g., y, such that y [not member of] S. Since [mathematical expression not reproducible], then there is at least one node in [mathematical expression not reproducible], e.g., z, such that z [not member of] S. Then, x, y, z belong to a connected component in [Q.sub.n]-E'-S. Condition 2 of Theorem 2 is satisfied.

In summary, [Q.sub.n]-E' is strong locally (k + 1)-diagnosable at the node v.

Clearly, the following corollary follows Theorem 4; hence, its proof is omitted.

Corollary 2. For n [greater than or equal to] 4 and E' [subset] E([Q.sub.n]) with 0 [less than or equal to] [absolute value of E'] [less than or equal to] n-3, [Q.sub.n]-E' is strongly r-diagnosable, where r represents the minimum degree of nodes in [Q.sub.n]-E'.

In the previous section, we concluded that the SLD of a node is its RD in an incomplete hypercube network [Q'.sub.n] created by removing the edge set E' [subset] E([Q.sub.n]) with [absolute value of E'] [less than or equal to] n-3 from [Q.sub.n]. In the following, we discuss the problem of the upper bound of [absolute value of E'] such that the following two conditions are satisfied: (1) the RD of each node in [Q.sub.n]-E', denoted by [Q'.sub.n], is at least 4; (2) the SLD of every node [Q'.sub.n] is the same as its RD. Now, we consider an example in which the SLD of a node in [Q'.sub.n] differs from its RD in [Q'.sub.n] with [absolute value of E'] = 7(n-3), even though the minimum degree of nodes in [Q'.sub.n] is more than 3. Assume that x, [x.sub.i] [member of] V, 1 [less than or equal to] i [less than or equal to] 7, the adjacent situations of which are shown in Figure 6. Let [mathematical expression not reproducible]. Let [mathematical expression not reproducible]. Since [absolute value of [F.sub.1]] = [absolute value of [F.sub.2]] = n + 1, ([F.sub.1], [F.sub.2]) is an indistinguishable pair; at the same time, N(x) [subset or equal to] [F.sub.1] [intersection] [F.sub.2], [t.sub.sl]([Q.sub.n]-E')(v) is not n, and the RD of v is n in [Q.sub.n]-E'.

Theorem 5. Let [Q'.sub.n] = [Q.sub.n]-E', where E' [subset] E([Q.sub.n]) with 0 [less than or equal to] [absolute value of E'] [less than or equal to] 7(n-3)-1. Assume that [delta]([Q'.sub.n]) [greater than or equal to] 3, then [for all] x [member of] V ([Q'.sub.n]), it follows that [mathematical expression not reproducible].

Proof 8. Before proving this theorem, we define some notions for further discussion. Consider another structure of a node v obtained by extending its type I structure, called the type I-EX structure of node v, in the following way: insert a node set [L.sub.4] and an edge set [E.sub.3] in the type I structure of node v, where [L.sub.4] = {u | (u, w) [member of] E, w [member of] [L.sub.3]}-[L.sub.2] and [E.sub.3] = {(u, w) | u [member of] [L.sub.3], w [member of] [L.sub.4]}. After removing E' from [Q.sub.n], the type I-EX structure of node v becomes another new structure, called the type II structure of node v. The set of nodes [L.sub.1] ([L.sub.2]; [L.sub.3]; [L.sub.4]) becomes another new set of nodes [L'.sub.1] ([L'.sub.2]; [L'.sub.3]; [L'.sub.4]) in the type II structure of node v. Similarly, the set of edges [E.sub.1] ([E.sub.2]; [E.sub.3]) becomes another new set of edges [E'.sub.1] ([E'.sub.2]; [E'.sub.3]) in the type II structure of node v. Let [mathematical expression not reproducible] with [absolute value of S] = l and 0 [less than or equal to] l [less than or equal to] h. By the type II structure of node v, we have that the number of nodes of connected component containing v in [Q'.sub.n]-S is smallest if and only if S [subset] [L'.sub.2]. So, we need to consider only the case of S [subset] [L.sub.2].

If [absolute value of S] = h, it is obtained that N(v) [subset or equal to] S, which satisfies Condition 2 of Theorem 2. Now, we consider the case of 0 [less than or equal to] [absolute value of S] [less than or equal to] h-1. For the sake of convenience, we introduce another new structure of node v, called type III structure of node v, which is obtained by removing S from the type II structure of node v. The set of nodes [L'.sub.1]([L'.sub.2]; [L'.sub.3]; [L'.sub.4]) becomes [L".sub.1]([L".sub.2]; [L".sub.3]; [L".sub.4]) in type III structure of node v. Similarly, the set of edges [E'.sub.1] ([E'.sub.2]; [E'.sub.3]) becomes another new set of edges [E".sub.1] ([E".sub.2]; [E".sub.3]) in the type III structure of node v. After deleting all nodes of S, we have [absolute value of [L".sub.1]] = 1 and [absolute value of [L".sub.2]] = h-l. Since for each v [member of] V([Q'.sub.n]), [mathematical expression not reproducible], it follows that [absolute value of [E".sub.1]] = h-l and [absolute value of [E".sub.2]] [greater than or equal to] 2(h-l). Moreover, by the definition of [Q.sub.n], we have that each node in [L".sub.3] is adjacent to at most two nodes in [L".sub.2]. Thus, it is true that [absolute value of [L".sub.3]] [greater than or equal to] ([absolute value of [E".sub.2]]/2) [greater than or equal to] h-l and [absolute value of [E".sub.3]] [greater than or equal to] h-l. Similarly, it is true that each node in [L".sub.4] is adjacent to at most three nodes in [absolute value of [L".sub.3]]; thus, [mathematical expression not reproducible]. Hence, for the component C, to which v in [Q'.sub.n]-S belongs, we have that [mathematical expression not reproducible]. To show that 2(h + 1-l) + 1 [less than or equal to] [absolute value of V(C)], which implies that Condition 1 of Theorem 2 holds, we consider the following cases:

Case 26 (h-l [greater than or equal to] 4). Since [mathematical expression not reproducible], it follows that [mathematical expression not reproducible].

Case 27 (h-l = 3). Note that [mathematical expression not reproducible]; hence, it is sufficient that V(C) [not equal to] 8. Suppose that V(C) = 8. Since h-l = 3, [absolute value of [L'.sub.1]] = 1, and [absolute value of [L'.sub.2]] = 3 in the type II structure of node v, the assumption that for each v [member of] V([Q'.sub.n]), [mathematical expression not reproducible] implies that [absolute value of [L'.sub.3]] = 4 or [L'.sub.3]] = 3. If [absolute value of [L'.sub.3]] = 4, then there exists some node [v.sub.0] [member of] [L'.sub.3] such that there is exactly one node in [L'.sub.3] that can connect to [v.sub.0]. Then, [L'.sub.4] has at least one node, e.g., [v'.sub.0], such that ([v.sub.0], [v'.sub.0]) [member of] E'. In other words, V(C) [greater than or equal to] 9, which contradicts the assumption that V(C) = 8. If [absolute value of [L'.sub.3]] = 3, then [for all]u [member of] [L'.sub.3], it follows that [mathematical expression not reproducible], which implies that there exist 7 nodes in [Q'.sub.n] whose RDs are all 3. This contradicts the assumption that 0 [less than or equal to] [absolute value of E'] [less than or equal to] 7(n-3)-1.

Case 28 (h-l = 2). Note that [mathematical expression not reproducible]; hence, it is sufficient that V(C) [not equal to] 6. Suppose that V(C) = 6. Since h-l = 2, it follows that [absolute value of [L'.sub.1]] = 1 and [absolute value of [L'.sub.2]] = 2 in the type II structure of node v. On the other hand, the assumption that for each [mathematical expression not reproducible], implies that [absolute value of [L'.sub.3]] = 3, where there exists at most one node in [L'.sub.3] that is shared by the two nodes in [L'.sub.2] as their common neighbor. Furthermore, [absolute value of [L'.sub.4]] [greater than or equal to] 1 can be obtained, which implies that V(C) [greater than or equal to] 7. This is a contradiction.

Case 29 (h-l = 1. Note that [mathematical expression not reproducible]; hence, it is sufficient that V(C) [not equal to] 4. Suppose that V(C) = 4. Since h-l=1, it follows that [absolute value of [L'.sub.1]] = 1 and [absolute value of [L'.sub.2]] = 1 in the Type II structure of node v. The assumption that for each [mathematical expression not reproducible] implies that [absolute value of [L'.sub.3]] [greater than or equal to] 2, which results in [absolute value of [L'.sub.4]] [greater than or equal to] 1. Hence, V(C) [greater than or equal to] 5, which contradicts the assumption that V(C) = 4.

By Theorem 5, we can obtain the following corollary.

Corollary 3. In [Q.sub.n] (n [greater than or equal to] 4), suppose that E' [subset] E([Q.sub.n]), with 0 [less than or equal to] [absolute value of E'] [less than or equal to] 7(n-3)-1. Then, [Q.sub.n]-E' is strongly r-diagnosable, where r represents the minimum degree of all nodes in [Q.sub.n]-E' and r [greater than or equal to] 3.

Finally, we discuss the situation where the RD of each node in [Q.sub.n]-E' exceeds 3.

Theorem 6. In [Q.sub.n] (n [greater than or equal to] 4), let E' [subset] E([Q.sub.n]), where [Q'.sub.n] = [Q.sub.n]-E'. If for each [mathematical expression not reproducible], then for any x [member of] V([Q'.sub.n]), it follows that [mathematical expression not reproducible].

Proof 9. We follow all definitions and terminologies mentioned in the proof of Theorem 5. Let S [subset] V([Q'.sub.n]), with [absolute value of S] = 1 and 0 [less than or equal to] l [less than or equal to] k. As in the proof of Theorem 5, we need to prove only that [absolute value of V(C)] [greater than or equal to] 2(k + 1-l) + 1 for 0 [less than or equal to] l [less than or equal to] k-1 and S [subset] [L.sub.2]. Since for each [mathematical expression not reproducible], we have that [mathematical expression not reproducible]. Therefore, we have that [mathematical expression not reproducible]. Thus, [mathematical expression not reproducible]. Then, we need to prove that [mathematical expression not reproducible]. Clearly, the result holds when 0 [less than or equal to] l [less than or equal to] k-1. Hence, for any [mathematical expression not reproducible].

By Theorem 6, we have the following corollary.

Corollary 4. In [Q.sub.n] (n [greater than or equal to] 4), let E' [subset] E([Q.sub.n]), where [Q'.sub.n] = [Q.sub.n]-E'. If min [mathematical expression not reproducible], then [Q'.sub.n] is strong locally r-diagnosable at each node.

5. Conclusions

For a system, if we consider only its global properties and ignore its local status, we may lose some interesting and important information. This paper proposes the concept of SLD and derives some conditions for testing the SLD of a node in a system. Moreover, we discuss the relationship between the SLD and the SD of a system. Based on this relationship, we obtain the SD of a system by determining the SLD of every node in the system. Our results show that the SLD of a node in [Q.sub.n] is n, where n [greater than or equal to] 4. Then, we consider the SLD of an incomplete hypercube network [Q.sub.n]-E', where E' [subset] E([Q.sub.n]). When 0 [less than or equal to] [absolute value of E'] [less than or equal to] n-3, the SLD of a node is the same as its RD in [Q.sub.n]-E'. The above mentioned result still holds in the following two cases: (1) 0 [less than or equal to] [absolute value of E'] [less than or equal to] 7 (n-3)-1, and for each v [member of] V([Q'.sub.n]), [mathematical expression not reproducible]. (2) No matter how many edges of E' exist, and for each v [member of] V([Q'.sub.n]), it follows that [mathematical expression not reproducible].

It is worth mentioning that haptic identification [25] is an important method of identification, and it is a natural idea to combine haptic identification with the strong local fault identification mentioned by the paper. Our future research work is to explore the strong local haptic identification of a system.

https://doi.org/10.1155/2018/5745628

Data Availability

The data used to support the findings of this study are included within the article

Conflicts of Interest

The authors declare that there is no conflict of interest regarding the publication of this paper.

Acknowledgments

This work was supported in part by the Natural Science Foundation of China under Grant no. 61862003 and no. 61761006 and in part by the Natural Science Foundation of the Guangxi Zhuang Autonomous Region of China under Grant no. 2016GXNSFAA380134.

References

[1] L. C. Ye and J. R. Liang, "Five-round adaptive diagnosis in Hamiltonian networks," IEEE Transactions on Parallel and Distributed Systems, vol. 26, no. 9, pp. 2459-2464, 2015.

[2] Z. Zhao, Y. Liu, and F. Luo, "Output feedback boundary control of an axially moving system with input saturation constraint," ISA Transactions, vol. 68, pp. 22-32, 2017.

[3] J. Fan, X. Jia, X. Liu, S. Zhang, and J. Yu, "Efficient unicast in bijective connection networks with the restricted faulty node set," Information Sciences, vol. 181, no. 11, pp. 2303-2315, 2011.

[4] J. Fan and X. Jia, "Edge-pancyclicity and path-embeddability of bijective connection graphs," Information Sciences, vol. 178, no. 2, pp. 340-351,2008.

[5] X. Li, J. Fan, C. K. Lin, and X. Jia, "Diagnosability evaluation of the data center network DCell," Computer Journal, vol. 61, no. 1, pp. 129-143, 2018.

[6] W. Yang and H. Lin, "Reliability evaluation of BC networks in terms of the extra vertex and edge-connectivity," IEEE Transactions on Computers, vol. 63, no. 10, pp. 2540-2548, 2014.

[7] W. Yang, H. Li, and X. Guo, "A kind of conditional fault tolerance of (n, k)-star graphs," Information Processing Letters, vol. 110, no. 22, pp. 1007-1011, 2010.

[8] J. Fan and X. Lin, "The t/k-diagnosability of the BC graphs," IEEE Transactions on Computers, vol. 54, no. 2, pp. 176-184, 2005.

[9] C. Yang, Y. Jiang, W. He, J. Na, Z. Li, and B. Xu, "Adaptive parameter estimation and control design for robot manipulators with finite-time convergence," IEEE Transactions on Industrial Electronics, vol. 65, no. 10, pp. 8112-8123, 2018.

[10] Y. Saad and M. H. Schultz, "Topological properties of hypercubes," IEEE Transactions on Computers, vol. 37, no. 7, pp. 867-872, 1988.

[11] F. P. Preparata, G. Metze, and R. T. Chien, "On the connection assignment problem of diagnosable systems," IEEE Transactions on Electronic Computers, vol. EC-16, no. 6, pp. 848-854, 1967.

[12] A. Sengupta and A. T. Dahbura, "On self-diagnosable multiprocessor systems: diagnosis by the comparison approach," IEEE Transactions on Computers, vol. 41, no. 11, pp. 1386-1396, 1992.

[13] C. F. Chiang and J. J. M. Tan, "Using node diagnosability to determine t-diagnosability under the comparison diagnosis model," IEEE Transactions on Computers, vol. 58, no. 2, pp. 251-259, 2009.

[14] P.-L. Lai, J. J. M. Tan, C.-P. Chang, and L.-H. Hsu, "Conditional diagnosability measures for large multiprocessor systems," IEEE Transactions on Computers, vol. 54, no. 2, pp. 165-175, 2005.

[15] S. L. Hakimi and A. T. Amin, "Characterization of connection assignment of diagnosable systems," IEEE Transactions on Computers, vol. C-23, no. 1, pp. 86-88, 1974.

[16] A. Kavianpour and K. H. Kim, "Diagnosabilities of hypercubes under the pessimistic one-step diagnosis strategy," IEEE Transactions on Computers, vol. 40, no. 2, pp. 232-237, 1991.

[17] Z. Zhao, X. Wang, C. Zhang, Z. Liu, and J. Yang, "Neural network based boundary control of a vibrating string system with input deadzone," Neurocomputing, vol. 275, pp. 1021-1027, 2018.

[18] L.-C. Ye, J.-R. Liang, and H.-X. Lin, "A fast pessimistic diagnosis algorithm for hypercube-like networks under the comparison model," IEEE Transactions on Computers, vol. 65, no. 9, pp. 2884-2888, 2016.

[19] W. Yang, H. Lin, and C. Qin, "On the t/k-diagnosability of BC networks," Applied Mathematics and Computation, vol. 225, no. 12, pp. 366-371, 2013.

[20] G. H. Hsu and J. J. M. Tan, "A local diagnosability measure for multiprocessor systems," IEEE Transactions on Parallel and Distributed Systems, vol. 18, no. 5, pp. 598-607, 2007.

[21] D. Wang, "The diagnosability of hypercubes with arbitrarily missing links," Journal of Systems Architecture, vol. 46, no. 6, pp. 519-527, 2000.

[22] D. West, Introduction to Graph Theory, Prentice Hall, 2001.

[23] A. Dahbura and G. Masson, "An 0([n.sup.2-5]) fault identification algorithm for diagnosable systems," IEEE Transactions on Computers, vol. C-33, no. 6, pp. 486-492, 1984.

[24] P. K. K. Loh, W. J. Hsu, and Y. Pan, "The exchanged hypercube," IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 9, pp. 866-874, 2005.

[25] C. Yang, K. Huang, H. Cheng, Y. Li, and C.-Y. Su, "Haptic identification by ELM-controlled uncertain manipulator," IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 47, no. 8, pp. 2398-2409, 2017.

Min Xie, (1,2) Jiarong Liang [ID], (2,3) and Xi Xiong (2,3)

(1) School of Automation Science and Engineering, South China University of Technology, 510640, China

(2) School of Computer and Electronics Information, Guangxi University, 530004, China

(3) School of Computer and Electronics Information, Guangxi Key Laboratory of Multimedia Communications and Network Technology, 530004, China

Correspondence should be addressed to Jiarong Liang; 13977106752@163.com

Received 15 April 2018; Revised 5 July 2018; Accepted 13 August 2018; Published 4 October 2018

Academic Editor: Michele Scarpiniti

Caption: Figure 1: An example of a distinguishable pair (X, Y).

Caption: Figure 2: Type I structure.

Caption: Figure 3

Caption: Figure 4: An illustration of the difference between the strong locally diagnosability and RD for a node in [Q'.sub.n].

Caption: Figure 5: Type I structure of the node v in [Q.sub.4].

Caption: Figure 6: Illustration of [t.sub.sl]([Q.sub.n]-E')(x) being equal to its RD.
COPYRIGHT 2018 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2018 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Xie, Min; Liang, Jiarong; Xiong, Xi
Publication:Complexity
Date:Jan 1, 2018
Words:11190
Previous Article:Multiple-Model Adaptive Estimation with A New Weighting Algorithm.
Next Article:A Method Adjusting Consistency and Consensus for Group Decision-Making Problems with Hesitant Fuzzy Linguistic Preference Relations Based on Discrete...

Terms of use | Privacy policy | Copyright © 2022 Farlex, Inc. | Feedback | For webmasters |