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

Authors: Min Xie; Jiarong Liang; Xi Xiong
Journal: Complexity
 (2018)

---

## Abstract

In the research on the reliability of a connection network, diagnosability is an important problem that should be considered. In this article, a new concept regarding diagnosability, called strong local diagnosability (SLD), which describes the local status of the strong diagnosability (SD) of a system, is presented. In addition, a few important results related to the SLD of a node of a system are presented. Based on these results, we conclude that in a hypercube network ofn dimensions, denoted by Qn, the SLD of a node is equal to its degree when n⩾4. Moreover, we explore the SLD of a node of an incomplete hypercube network. We determine that the SLD of a node is equal to its remaining degree (RD) in an incomplete hypercube network, which is true provided that the number of faulty edges in this hypercube network does not exceed n−3. Finally, we discuss the SLD of a node for an incomplete hypercube network and obtain the following results: if the minimum RD of nodes in an incomplete hypercube network of n-dimensions is greater than 3, then the SLD of any node is still equal to its RD provided that the number of faulty edges does not exceed 7n−3−1. If the RD of each node is greater than 4, then the SLD of each node is also equal to its RD, no matter how many faulty edges exist in Qn.


---

## Body

## 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 Qn, consists of 2n nodes and n2n−1 edges. A binary n-bit string, e.g., x1x2,…,xn, can be employed to denote the address of a node x in Qn. 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 Qn, 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. Qn can be decomposed in two n−1-dimensional hypercube networks Qn−10 and Qn−11 along the ith-dimensional edges. Let v0∈VQn−10. Then there must be another node v1∈VQn−11 satisfying v0,v1∈EQn. We call this edge the crossing edge between Qn−10 and Qn−11.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 t-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 Qn; the number of node subsets such that its cardinality is n is C2nn. However, the number of node subsets such that its size is n and it incorporates all neighbors of some node is at most 2n. The ratio 2n/C2nn 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, letS denote the integrating system produced by Qr and Qs, 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 Qn is n, where n⩾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 Section3, 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 Qn is studied. Finally, in Section 5, we discuss the conclusions of our paper.


## 2. Preliminaries

A system is usually described by a graphHV,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 HV,E, a node v is said to be its neighbor if u,v∈E. Moreover, let NHz=y∣y,z∈E (Nz, in no confusion) represent the set of all neighbors of z. The degree of a node z in H, denoted by degHz (degz, no confusion), is the cardinality of Nz, i.e., degz=Nz. 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 kH, is the cardinality of the minimum node set X (X⊂V) such that H−X is disconnected. If kH⩾r, then H is said to be r-connected. For a graph HV,E, we use VH (EH, respectively) to denote the node set of H (the edge set of H, respectively).In the PMC model, ifx,y∈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 σx,y=1 (σx,y=0). We use σ=σx,y∣x,y∈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 tH. Given a syndrome σ, a set S⊆VH is called consistent with σ if the following condition is true: if ∀x∈VH−S and x,y∈E, then σx,y=1 if and only if y∈S.We useσS to denote the set of syndromes produced by faulty node set S. Two subsets X,Y⊆VH are called distinguishable if σX∩σY=∅. 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ΔY=X−Y∪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 systemHV,E is t-diagnosable if and only if for two arbitrary different subsets X,Y⊂V satisfying ∣X∣⩽t,∣Y∣⩽t, X,Y is always a distinguishable pair.Lemma 2 (see [23]).
In a systemHV,E, suppose that X,Y⊂V with ∣X∣⩽t,∣Y∣⩽t are two different subsets. Then X,Y is a distinguishable pair if and only if H has at least an edge x,y∈E such that x∈V−X−Y and y∈XΔY (Figure 1).Figure 1
An example of a distinguishable pairX,Y.
(a)
(b)The following lemmas are related to the concept of node diagnosability:Lemma 3 (see [20]).
Suppose thatHV,E is a system, z∈V. H is locally t-diagnosable at z if and only if for each subset X⊂V with ∣X∣=l, l∈0,1,⋯,t−1, and z∉X, the number of nodes in the connected component containing z in H−X is greater than 2t−l.Lemma 4 (see [20]).
Suppose thatHV,E is a graph, v∈V with degv=k. Then, the locally diagnosability (LD) of node v does not exceed k.Lemma 5 (see [20]).
In a systemHV,E, suppose that z∈V. Then the system HV,E is t-diagnosable at node z∈VG if and only if for two arbitrary different subsets X,Y⊂VH satisfying ∣X∣⩽t,∣Y∣⩽t and z∈XΔY, H has at least an edge x,y∈E such that x∈V−X−Y and y∈XΔY.Lemma 6 (see [20]).
At-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 Lemma1 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 stronglyt-diagnosable system follows [14].Definition 2.
At-diagnosable system, denoted by HV,E, is called a strong t-diagnosable system if the following condition is true.
For any two different subsetsX,Y⊂V with ∣X∣⩽t+1 and ∣Y∣⩽t+1, if X,Y is an indistinguishable pair, then H has at least a node x such that Nx⊆X∩Y.
The strong diagnosability (SD) of a system is the maximum number value oft 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 HV,E, x∈V, we use tH (tlHx; tslHx) to denote the diagnosability of HV,E (the LD at node x in HV,E; the SLD at node x in HV,E).Definition 3.
LetHV,E be the diagnostic graph of a system H and x∈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 subsetsX,Y⊂V with ∣X∣⩽t+1,∣Y∣⩽t+1 and x∈XΔY, if X,Y is an indistinguishable pair, then Nx⊆X∩Y.
A systemH 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 thatHV,E is a graph, y∈V with degy=k. The SLD of node y in HV,E does not exceed k.Proof 1.
By Lemma4 and Definition 3, the proof can be easily obtained.In the following, we propose two propositions for describing the relationship between a strong locallyt-diagnosable system and a strongly t-diagnosable system:Proposition 2.
IfHV,E is strong locally t-diagnosable, then HV,E is strongly t-diagnosable.Proof 2.
Suppose thatHV,E is not strongly t-diagnosable. From Definition 1, it is obtained that there is an indistinguishable pair X,Y with X,Y⊂V,X≠Y, ∣X∣⩽t+1, and ∣Y∣⩽t+1 such that for any node x∈V, Nx⊄X∩Y. Since X≠Y, there exists a node y such that y∈XΔY and Ny⊄X∩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 systemS 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.
LetHV,E be a triangle-free system and t⩾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 Proposition2, the sufficiency holds.Necessity 1.
LetH be a strongly t-diagnosable system; then, H is t-diagnosable. Let x∈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⊂V with ∣X∣⩽t+1 and ∣Y∣⩽t+1, if X,Y is an indistinguishable pair, then H has at least a node x∈XΔY and Nx⊆X∩Y. In contrast, assuming that Nx⊈X∩Y, we derive a contradiction. By Definition 2, there is at least one node y∈V such that Ny⊆NX∩NY. By Lemma 4, we have that ∣X∩Y∣⩾∣Ny∣⩾t. Note that X≠Y, ∣X∣⩽t+1, and ∣Y∣⩽t+1; therefore, ∣X∩Y∣⩽t. Thus, ∣X∩Y∣=∣Ny∣=t. On the other hand, x∈XΔY implies that x∈X−Y or x∈Y−X. Here, we need to consider only the situation where x∈X−Y, as the proof of the situation in which x∈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∈X−Y, (2) y∈Y−X, (3) y∈X∩Y, and (4) y∈V−X∪Y.Case 1y∈X−Y.
Since∣X−Y∣⩽1 and X≠Y, x=y, which is a contradiction.Case 2y∈Y−X.
It is clear thatY−X=y,X−Y=x. X,Y is an indistinguishable pair, implying that Nx∩V−X∪Y=ϕ. Moreover, by Nx⊈X∩Y, we have that y∈Nx. This is a contradiction to Ny⊆X∩Y.Case 3y∈X∩Y.
Since∣X∩Y∣=∣Ny∣=t and Ny⊆X∩Y, Ny=X∩Y, which is a contradiction.Case 4y∈V−X∪Y.
By the hypothesis, we have thatX−Y=x and Y−X⩽1. We first discuss the situation where 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∪Y. Nx∩V−X∩Y=ϕ (as X,Y is an indistinguishable pair) and Nx⩾t (Lemma 4), we have that Nx∪X∪Y⩾t−1. Since H is a triangle-free graph, Nz∩X∩Y⩽1. Thus, the degree of z is no greater than 2, a contradiction to degz⩾t⩾3 (Lemma 4). Second, we consider the situation where Y−X=0. Since there is no edge between x and any node in V−X∪Y, Nx⊆X∪Y; thus, Nx⊆X, and therefore, Nx∪x⊂X. On the other hand, since Nx⩾t, X=x∪Nx, and hence, Y=Nx, which is a contradiction. This completes the proof.Proposition2 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 systemHV,E, the strong diagnosability of H is equal to mintheSLDatnoder∣r∈V.The following sufficient and necessary condition can be applied.Theorem 2.
In a graphHV,E, x∈V. Thus, HV,E is strong locally t-diagnosable at node x if and only if, for any S⊂V, ∣S∣=l, l∈0,1,⋯,t, and x∉S, the following conditions hold:
Condition 1
Ifl≠t, then the number of nodes of the connected component containing x in H−S exceeds 2t+1−l.Condition 2
Ifl=t, then either (a) the number of nodes of the connected component containing x in H−S exceeds 2 or (b) Nx⊆S.Proof 4 (sufficiency).
LetC denote the connected component containing x in H−S. By Condition 1, for l≠t, we have that 2t−l+1<2t+1−l+1⩽∣VC∣. 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⊂V with ∣X∣⩽t+1, ∣Y∣⩽t+1 and x∈XΔY, if X,Y is an indistinguishable pair, then Nx⊆X∩Y. Suppose that there exist two different subsets X,Y⊂V with ∣X∣⩽t+1, ∣Y∣⩽t+1 and x∈XΔY such that X,Y is an indistinguishable pair and Nx⊈X∩Y. Let S′=X∩Y; then, ∣S′∣=l⩽t. If l≠t, by Condition 1, the number of nodes of the connected component containing x in H−S′ is greater than 2t+1−l. Moreover, the number of nodes of the connected component containing x in H−S′ is greater than ∣XΔY∣, which implies that H has two nodes y∈V−X∪Y and z∈XΔY such that y,z∈E. Hence, X,Y is a distinguishable pair, which is a contradiction. Thus, ∣S′∣=l=t, which implies that ∣XΔY∣⩽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∈V−X∪Y and z∈XΔY such that y,z∈E. Hence, X,Y is a distinguishable pair, which is a contradiction.Next, we consider the situationl=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⊂V with ∣X∣⩽t+1, ∣Y∣⩽t+1 and x∈XΔY, if X,Y is an indistinguishable pair, then Nx⊆X∩Y. To the contrary, assume that there exist two different subsets X,Y⊂V with ∣X∣⩽t+1, ∣Y∣⩽t+1, x∈XΔY and X,Y is an indistinguishable pair, but Nx⊈X∩Y. Let S′=X∩Y and ∣S′∣=r, then 0⩽r⩽t, and then we have that ∣XΔY∣⩽2t+1−r. Moreover, by Condition 1, we have that r=t, which implies that ∣XΔY∣⩽2. Since X,Y is an indistinguishable pair, there is no edge from V−X∪Y to XΔY. So, the number of nodes of the connected component containing x is no more than ∣XΔY∣⩽2. Moreover, Nx⊆S′=X∩Y, a contradiction.Necessity 2.
We consider Condition 1 first. Suppose that for somel∈0,1,⋯,t−1, H−S has a connected component containing x, e.g., C, such that ∣VC∣⩽2t+1−1. Let VC be decomposed in two subsets as follows: R1∩R2=∅ and R1∪R2=VC, with ∣R1∣⩽t+1−l and ∣R2∣⩽t+1−l. Let X=R1∪S and Y=R2∪S. It is clear that ∣X∣⩽t+1, ∣Y∣⩽t+1 and x∈XΔY. Since C is a connected component of H−S, H does not have an edge y,z∈E such that y∈XΔY and z∈V−X∪Y. By Lemma 2, X,Y is an indistinguishable pair. Since H is strong locally t-diagnosable at node x, Nx⊆S. Hence, ∣Nx∣⩽∣S∣⩽l⩽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 ∣Nx∣⩾t, which is a contradiction. Hence, Condition 1 is necessary.
Now, let us consider Condition 2. Suppose that∣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 VL can be decomposed in two subsets R1 and R2 satisfying the following conditions: R1∩R2=∅ and R1∪R2=VL, with ∣R1∣⩽1 and ∣R2∣⩽1. Let X=R1∪S and Y=R2∪S. Then, ∣X∣⩽t+1,∣Y∣⩽t+1, and x∈XΔY. By the assumption that HV,E is strong locally t-diagnosable at node x, we have that HV,E is locally t-diagnosable at node x. Moreover, we have that X,Y is an indistinguishable pair. By Definition 3, we conclude that Nx⊆X∩Y=S. This completes the proof of necessity.Corollary 1.
Suppose thatH′V′,E′ is a subgraph of HV,E, y∈V′. If H′V′,E′ is strong locally t-diagnosable at y and NHy⊆V′, then HV,E is strong locally t-diagnosable at y.Proof 5.
For anyS⊂V, ∣S∣=l, l∈0,1,⋯,t, and x∉S. We will prove that the two conditions in Theorem 2 hold. Let S′=S∩V′, l′=∣S′∣. Consider the following cases:Case 5l≠t.
Note thatl′≠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 2t+1−l′, which implies the number of nodes of the connected component containing y in H−S exceeds 2t+1−l′. Moreover, the number of nodes of the connected component containing y in H−S exceeds 2t+1−l. So, Condition 1 of Theorem 2 holds.Case 6l=t.Case 7l′≠t.
An argument being similar to Case5 can be used to obtain the following result: the number of nodes of the connected component containing y in H′−S′ exceeds 2t+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 8l′=t.
ThenS′=S. Since H′V′,E′ is strong locally t-diagnosable at y and NHy⊆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) NH′y⊆S′, which implies NHy⊆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 thatHV,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 (L1, L2, and L3) and two edge sets (E1, E2), as shown in Figure 2. These sets are defined as follows: L1=x, L2=y∣y,x∈E, and L3=z∣z,y∈E,y∈L2. E1=x,y∣x∈L1,y∈L2, and E2=y,z∣y∈L2,z∈L3. Let Nn (Ne) represent the number of nodes (edges) in the type I structure.Figure 2
TypeI 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
n is strong locally n-diagnosable at each node, where n⩾4.Proof 6.
Letv∈VQn be an arbitrary node. For each S⊂VQn, ∣S∣=l, l∈0,1,⋯,n, and v∉S, we show that the two conditions of Theorem 2 are both true.Case 9l≠n.
Noting that the connectivity ofQn is n, we have that Qn−S is connected. Let C denote this unique connected component in Qn−S; then, v∈VC. Hence, ∣VC∣=2n−l⩾2t+1−l+1 (n⩾4), which implies that Condition 1 of Theorem 2 holds.Case 10l=n.
Consider the type I structure of nodev in Qn. If S⊆L2, then Nv⊆S, which implies that Condition 2 of Theorem 2 is true. If S⊈L2, then there are two nodes u,w satisfying u∈L2,w∈L3, and v,u∈E1,u,w∈E2. Hence, Qn−S has a connected component, which incorporates v and has 3 or more nodes. This completes the proof of Theorem 3.According to Theorem3, the SLD of every node of Qn is the same as its degree, with n⩾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′⊂E to denote an edge subset and Qn′ to denote an incomplete hypercube network of n dimensions created by removing E′ from the hypercube network Qn. In the following, we show that the SLD of every node is the same as its RD in Qn′, 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, degx=n. Let E′=x,u∈E∣u∈V−x,y−x,v, where u and v are two neighbors of x; then, ∣E′∣=n−2. Let X=NQn′v−x∪v,y and Y=NQn′v∪y; then, ∣X∣=∣Y∣=n+1, v∈XΔY. By Lemma 2, X,Y is an indistinguishable pair, and Nv⊂X∩Y. Hence, the SLD of node v differs from its RD in Qn′.Theorem 4.
LetE′⊂EQn be an edge subset with 0⩽∣E′∣⩽n−3, where n⩾4. Let Qn′ denote the induced subgraph of EQn−E′. Then, the SLD of every node of Qn′ is exactly the same as its RD.Proof 7.
We prove this theorem by inductionn. First, let us consider the situation where n=4; in this case, ∣E′∣⩽1. For ∣E′∣=0, based on Theorem 3, the result holds. Assume that ∣E′∣=1. We consider the type I structure of node v in Q4, as shown in Figure 4. It is clear that ∣L1∣+∣L2∣+∣L3∣=1+4+6=11. If E′⊂E1, 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′⊂E2, then the RD of v is 4. Let S⊂VQ4′ and v∈S, with ∣S∣=l and 0⩽l⩽4. When l=4 and Nv⊆S, Condition 2 of Theorem 2 holds. When l=4 and Nv⊆S, consider the following cases.Case 11∣Nv−S∣⩾2.
Then the number of nodes of the connected component containingv in Q4′−S is at least 3, Condition 2 of Theorem 2 holds.Case 12∣Nv−S∣=1.
Then∣Nv∩S∣=3. Let u∈Nv−S, then Nu∩L3 has at least 2 nodes, which implies ∣Nu∩L3−S∣⩾1. So, the number of nodes of connected component containing v in Q4′−S is at least 3. In other words, Condition 2 of Theorem 2 holds.Figure 3Figure 4
An illustration of the difference between the strong locally diagnosability and RD for a node inQn′.Next, we show that when0⩽l⩽3, ∣VC∣⩾24+1−l+1=11−2l, where C is the connected component containing v in Q4′−S. From Figure 5, we conclude that the only case stopping the condition from being satisfied is that in which S=v2,v3,v4 and E′=v1,v11. However, based on the definition of a hypercube network, the connected component C contains other neighbors of v1, e.g., v12 and v13, as well as their neighbors, which do not include v1. Hence, for connected component C, it is true that ∣VC∣⩾5 when l=3. In summary, for n=4, the result is true.Figure 5
Type I structure of the nodev in Q4.Assume that whenn⩾5 for Qn−1′, the result is true. Next, we prove that for n⩾5, Qn′ and 0⩽∣E′∣⩽n−3, the result is still true. If ∣E′∣=0, then the result holds. Now, we consider the situation where 1⩽∣E′∣⩽n−3. Decompose Qn in two- n−1 dimensional hypercube networks Qn−10 and Qn−11 along the ith-dimensional edges. Let E0′=EQn−10∩E′, E1′=EQn−11∩E′. Let v be an arbitrary node. Without the loss of generality, let v∈VQn−10 and degQn−10−E0′v=k. Suppose that v,v′∈EQn is a crossing edge, namely, v,v′∈EQn is one of the ith-dimensional edges, where v′∈VQn−11. Consider the following two cases:Case 13v,v′∈E′.
Then,0⩽∣E0′∣⩽n−1−3. By the inductive hypothesis, we have that tslQn−10−E0′v=k. On the other hand, we have that degQn−E′v=k. According to Corollary 1 and Proposition 1, we have that k=tslQn0−E0′v⩽tslQn−E′v⩽degQn−E′v=k. Hence, tslQn−E′v=k, and thus the result is true.Case 14v,v′∉E′.
Then,degQn−E′v=k+1. By Proposition 1, we have that tslQn′−E′v⩽k+1. Now, we need to prove only that Qn−E is strong locally k+1-diagnosable at node v. Let S⊂VQn−E′, with v∉S, 0⩽∣S∣=l⩽k+1, S0=S∩VQn−10−E0′, and S1=S∩VQn−11−E1′. 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 Qn−E′−S, C0 denote the connected component containing v in Qn−10−E0′−S0, and C1 denote the connected component containing v′ in Qn−11−E1′−S1; moreover, let si=Si,i=0,1.Case 15.
First, we consider the condition thatl⩽k. We will prove that ∣VC∣⩾2k+1+1−l+1. Consider the following cases:Case 16∣E0′∣=n−3.Case 17v′∉S.
Ifs1⩽n−2, then ∣VC1∣⩾2n−1−s1. Moreover, ∣VC∣⩾∣VC1∪v∣⩾2n−1+1−l⩾2k+1+1−l+1. If s1=n−1, then ∣VC0∣=2n−1. Moreover, ∣VC∣⩾∣VC0∪v′∣⩾2n−1+1⩾2k+1+1−l+1.Case 18v′∈S.
It is obvious thats0⩽k−1. Let x,y∈E0′; then, x,y has at least one node, e.g., x, which is not v. Let S¯0=S0∪x; then, ∣S¯0∣⩽s0+1⩽k.If∣S¯0∣⩽k−1, let C¯0 denote the connected component containing v in Qn−10−E0′−x,y−S¯0. Since Qn−10−E0′−x,y−S¯0 is the subgraph of Qn−10−E0′−S0, ∣VC0∣⩾∣VC¯0∣. Note that ∣E0′−x,y∣=n−1−3; by inductive hypothesis and Theorem 2, we have that ∣VC¯0∣⩾2k+1−s0+1+1. In Qn−10−E0′−S0, 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 Qn, where u′,w′∈VQn−11 and u,u′,w,w′∈E. If s1=1, then VC¯0∪u′,w′⊂VC, and then ∣VC∣⩾∣VC¯0∣+2⩾2k+1−s0+1+1+2=2k+1+1−l+1. If s11, then s0+1⩽l−1, and then ∣VC∣⩾∣VC¯0∣⩾2k+1−s0+1+1⩾2k+1+1−l+1.If∣S¯0∣=k, then s1=1,s0=k−1. Since degQn−10−E0′v=k, there must exist one neighbor of v, e.g., z, such that z≠x in Qn−10−E0′−x,y−S¯0. Let z,z′ be a crossing edge in Qn, where z′∈VQn−11. Let Cz′ denote the connected component containing z′ in Qn−11−E1′−S1; then, ∣VCz′∣⩾2n−1−s1. Note that z,z′∉E′; we have that v,z,z′ belong to a connected component of Qn−E′, which implies that ∣VC∣⩾∣VCz′∪v,z∣⩾2n−1+2−s1⩾2k+1+1−l+1.Case 19∣E0′∣=0.Ifv′∈S, then s0⩽k−1⩽n−2. Since the connectivity of Qn−1 is n−1, ∣VC0∣⩾2n−1−s0⩾2k+1+1−l+1. Hence, ∣VC∣⩾∣VC0∣⩾2k+1+1−l+1. If v′∉S, then either ∣VC0∣⩾2n−1−s0⩾2k+1+1−l+1 or ∣VC1∣⩾2n−1−s1⩾2k+1+1−l+1. Hence, ∣VC∣⩾2k+1+1−l+1.Case 201⩽∣E0′∣⩽n−1−3.
Next, we show that∣VC∣⩾2k+1+1−l+1. Since 0⩽∣E1′∣⩽n−3−1, the degree of any node in Qn−11−E1′ is at least 3. Therefore, v′ has two neighbors, e.g., x and y, in Qn−11−E1′. Consider the following cases:Case 210⩽l⩽k−1.
By inductive hypothesis and Theorem2, we have that VC0⩾2k+1−s0+1. If S⊂VQn−10−E0′, then ∣VC∣⩾∣VC0∣+∣v′,x,y∣⩾2k+1−l+1+3⩾2k+1+1−l+1. If S⊆VQn−10−E0′, then ∣VC∣⩾∣VC0∣⩾2k+1−l−1+1=2k+1+1−l+1.Case 22l=k.
Since0⩽∣E1′∣⩽n−3−1, there exists another neighbor of v′, e.g., v11′, in Qn−11−E1′. If S⊆Qn−10−E0′, then ∣VC1∣⩾2n−1, and then ∣VC∣⩾∣VC1∪v∣⩾2n−1+1⩾2k+1+1−l+1. If S⊆Qn−10−E′, then s0⩽k−1. Hence, by inductive hypothesis and Theorem 2, we have that ∣VC0∣⩾2k+1−s0+1⩾2k+1−l+1.Case 23.
Next, we consider the condition thatl=k+1. Suppose that NQn′v⊆S. Consider the following cases.Case 24v′∉S.
Since∣NQn−11−E1′v′∣+∣NQn−10−E0′v∣⩾2n−1−n−3=n+1>k+1=∣S∣, there is at least node y in NQn−11−E1′v′∪NQn−10−E0′v such that y∉S. Hence, y,v,v′ belong to a connected component in Qn−E′−S. Condition 2 of Theorem 2 is satisfied.Case 25v′∈S.
ByNQn−E′v⊈S, we conclude that there exists at least node in NQn−10−E0′v, e.g., y, such that y∉S. Since NQn−1−E′v,y⩾n+1>k+1=∣S∣, then there is at least one node in NQn−E′, e.g., z, such that z∉S. Then, x,y,z belong to a connected component in Qn−E′−S. Condition 2 of Theorem 2 is satisfied.In summary,Qn−E′ is strong locally k+1-diagnosable at the node v.Clearly, the following corollary follows Theorem4; hence, its proof is omitted.Corollary 2.
Forn⩾4 and E′⊂EQn with 0⩽∣E′∣⩽n−3, Qn−E′ is strongly r-diagnosable, where r represents the minimum degree of nodes in Qn−E′.In the previous section, we concluded that the SLD of a node is its RD in an incomplete hypercube networkQn′ created by removing the edge set E′⊂EQn with ∣E′∣⩽n−3 from Qn. In the following, we discuss the problem of the upper bound of ∣E′∣ such that the following two conditions are satisfied: (1) the RD of each node in Qn−E′, denoted by Qn′, is at least 4; (2) the SLD of every node Qn′ is the same as its RD. Now, we consider an example in which the SLD of a node in Qn′ differs from its RD in Qn′ with ∣E′∣=7n−3, even though the minimum degree of nodes in Qn′ is more than 3. Assume that x,xi∈V,1⩽i⩽7, the adjacent situations of which are shown in Figure 6. Let Hxi=Nxi−x1,x2,⋯,x7, Ei=y,xi∈E∣y∈Hxi, and E′=E1∪E2∪⋯∪E7; then, ∣E′∣=7n−3. Let F1=Nx−x5∪x,x2 and F2=Nx−x1,x3∪x4,x6,x7. Since ∣F1∣=∣F2∣=n+1, F1,F2 is an indistinguishable pair; at the same time, Nx⊆F1∩F2, tslQn−E′v is not n, and the RD of v is n in Qn−E′.Theorem 5.
LetQn′=Qn−E′, where E′⊂EQn with 0⩽∣E′∣⩽7n−3−1. Assume that δQn′⩾3, then ∀x∈VQn′, it follows that tslQn′x=degQn′x.Proof 8.
Before proving this theorem, we define some notions for further discussion. Consider another structure of a nodev obtained by extending its type I structure, called the type I-EX structure of node v, in the following way: insert a node set L4 and an edge set E3 in the type I structure of node v, where L4=u∣u,w∈E,w∈L3−L2 and E3=u,w∣u∈L3,w∈L4. After removing E′ from Qn, the type I-EX structure of node v becomes another new structure, called the type II structure of node v. The set of nodes L1 (L2; L3; L4) becomes another new set of nodes L1′ (L2′; L3′; L4′) in the type II structure of node v. Similarly, the set of edges E1 (E2; E3) becomes another new set of edges E1′ (E2′; E3′) in the type II structure of node v. Let degQn−E′v=h and S⊂VQn with ∣S∣=l and 0⩽l⩽h. By the type II structure of node v, we have that the number of nodes of connected component containing v in Qn′−S is smallest if and only if S⊂L2′. So, we need to consider only the case of S⊂L2.Figure 6
Illustration oftslQn−E′x being equal to its RD.If∣S∣=h, it is obtained that Nv⊆S, which satisfies Condition 2 of Theorem 2. Now, we consider the case of 0⩽∣S∣⩽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 L1′L2′;L3′;L4′ becomes L1′′L2′′;L3′′;L4′′ in type III structure of node v. Similarly, the set of edges E1′ (E2′; E3′) becomes another new set of edges E1′′ (E2′′; E3′′) in the type III structure of node v. After deleting all nodes of S, we have ∣L1′′∣=1 and ∣L2′′∣=h−l. Since for each v∈VQn′, degQn′v⩾3, it follows that ∣E1′′∣=h−l and ∣E2′′∣⩾2h−l. Moreover, by the definition of Qn, we have that each node in L3′′ is adjacent to at most two nodes in L2′′. Thus, it is true that ∣L3′′∣⩾E2′′/2⩾h−l and ∣E3′′∣⩾h−l. Similarly, it is true that each node in L4′′ is adjacent to at most three nodes in L3′′; thus, ∣L4′∣⩾E3′/3⩾h−l/3. Hence, for the component C, to which v in Qn′−S belongs, we have that ∣VC∣⩾1+2h−l+h−l/3. To show that 2h+1−l+1⩽∣VC∣, which implies that Condition 1 of Theorem 2 holds, we consider the following cases:Case 26h−l⩾4.
Sinceh−l/3⩾2, it follows that ∣VC∣⩾1+2h−l+h−l/3⩾2h+1−l+1.Case 27h−l=3.
Note that2h+1−l+1=9 and 1+2h−l+h−l/3=8; hence, it is sufficient that VC≠8. Suppose that VC=8. Since h−l=3, ∣L1′∣=1, and ∣L2′∣=3 in the type II structure of node v, the assumption that for each v∈VQn′, degQn′v⩾3 implies that ∣L3′∣=4 or ∣L3′∣=3. If ∣L3′∣=4, then there exists some node v0∈L3′ such that there is exactly one node in L3′ that can connect to v0. Then, L4′ has at least one node, e.g., v0′, such that v0,v0′∈E′. In other words, VC⩾9, which contradicts the assumption that VC=8. If ∣L3′∣=3, then ∀u∈L3′, it follows that degQn′u=3,∣L4′∣=1,∣E3′∣=3, which implies that there exist 7 nodes in Qn′ whose RDs are all 3. This contradicts the assumption that 0⩽∣E′∣⩽7n−3−1.Case 28h−l=2.
Note that2h+1−l+1=7 and 1+2h−l+h−l/3=6; hence, it is sufficient that VC≠6. Suppose that VC=6. Since h−l=2, it follows that ∣L1′∣=1 and ∣L2′∣=2 in the type II structure of node v. On the other hand, the assumption that for each v∈VQn′, degQn′v⩾3 implies that ∣L3′∣=3, where there exists at most one node in L3′ that is shared by the two nodes in L2′ as their common neighbor. Furthermore, ∣L4′∣⩾1 can be obtained, which implies that VC⩾7. This is a contradiction.Case 29h−l=1.
Note that2h+1−l+1=5 and 1+2h−l+h−l/3=4; hence, it is sufficient that VC≠4. Suppose that VC=4. Since h−l=1, it follows that ∣L1′∣=1 and ∣L2′∣=1 in the Type II structure of node v. The assumption that for each v∈VQn′, degQn′v⩾3 implies that ∣L3′∣⩾2, which results in ∣L4′∣⩾1. Hence, VC⩾5, which contradicts the assumption that VC=4.By Theorem5, we can obtain the following corollary.Corollary 3.
InQn (n⩾4), suppose that E′⊂EQn, with 0⩽∣E′∣⩽7n−3−1. Then, Qn−E′ is strongly r-diagnosable, where r represents the minimum degree of all nodes in Qn−E′ and r⩾3.Finally, we discuss the situation where the RD of each node inQn−E′ exceeds 3.Theorem 6.
InQn (n⩾4), let E′⊂EQn, where Qn′=Qn−E′. If for each v∈VQn′, degQn′v>3, then for any x∈VQn′, it follows that tslQn′x=degQn′x.Proof 9.
We follow all definitions and terminologies mentioned in the proof of Theorem5. Let S⊂VQn′, with ∣S∣=l and 0⩽l⩽k. As in the proof of Theorem 5, we need to prove only that ∣VC∣⩾2k+1−l+1 for 0⩽l⩽k−1 and S⊆L2. Since for each v∈VQn′, degQn′v>3, we have that ∣L1′∣=1, ∣L2′∣=k−l and ∣E1′∣=k−l, E2′⩾3k−l. Therefore, we have that ∣L3′∣⩾E2′/2⩾3k−l/2, ∣E3′∣⩾4−2∣L3′∣⩾3k−l and ∣L4′∣⩾E3′/3⩾k−l. Thus, ∣VC∣⩾∣L1′∣+∣L2′∣+∣L3′∣+∣L4′∣⩾1+k−l+3k−l/2+k−l=2k−l+1+3k−l/2. Then, we need to prove that 3k−l/2⩾2. Clearly, the result holds when 0⩽l⩽k−1. Hence, for any x∈VQn′, tslQn′x=degQn′x.By Theorem6, we have the following corollary.Corollary 4.
InQn (n⩾4), let E′⊂EQn, where Qn′=Qn−E′. If mindegQn′v∣v∈V=r⩾4, then Qn′ 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 inQn is n, where n⩾4. Then, we consider the SLD of an incomplete hypercube network Qn−E′, where E′⊂EQn. When 0⩽∣E′∣⩽n−3, the SLD of a node is the same as its RD in Qn−E′. The above mentioned result still holds in the following two cases: (1) 0⩽∣E′∣⩽7n−3−1, and for each v∈VQn′, degQn′v⩾3. (2) No matter how many edges of E′ exist, and for each v∈VQn′, it follows that degQn′v>3.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.



---

*Source: 5745628-2018-10-04.xml*