A Proof for g-Good-Neighbor Diagnosability of Exchanged Hypercubes ()
1. Introduction
A multiprocessor system and interconnection network have an underlying topology, which is usually presented by a graph, where nodes represent processors and links represent communication links between processors. Some processors may fail in the system and processor fault identification plays an important role in reliable computing. The identification process is called the diagnosis of the system. Several diagnosis models were proposed to identify the faulty processors. One major approach is the Preparata, Metze, and Chien’s (PMC) diagnosis model introduced by Preparata et al. [1] . Under the PMC model, the diagnosis of the system is achieved through two linked processors testing each other. Another major approach, namely, the comparison diagnosis model (MM model), was proposed by Maeng and Malek [2] . Under the MM model, to diagnose a system, a node sends the same task to two of its neighbors, and then compares their responses. The MM* is a special case of the MM model and each node must test all pairs of its adjacent nodes of the system. The diagnosability of the system is one important study topic. In 2012, Peng et al. [3] proposed measurement for fault diagnosis of the system, namely, the g-good-neighbor diagnosability (which is also called the g-good-neighbor conditional diagnosability), which requires that every fault-free node has at least g fault-free neighbors. Numerous studies have been investigated under the PMC and the MM model or the MM* model, see [2] - [23] .
Let
be the exchanged hypercube with
. In this paper, we show the following: 1) The g-good-neighbor diagnosability of
is
under the PMC model for any g with
. 2) The diagnosability of
under the MM* model is
for
. 3) The g-good-neighbor diagnosability of
under the MM* model is
for
and any g with
.
The rest of this paper is organized as follows: In Section 2, we provide the terminology and preliminaries for the system diagnosis. In Section 3, we shall show the g-good-neighbor diagnosability of the exchanged hypercube under the PMC model and the MM* model. Finally, the conclusion is given in Section 4.
2. Preliminaries
A multiprocessor system and a network are modeled as an undirected simple graph
,
denotes processors and
denotes communication links. For
with
, the subgraph of G induced by
, denoted by
. For
with
, the symmetric difference
is
. For
, the neighborhood
of v in G to be the set of vertices adjacent to v. Let
. The set
is denoted by
. For graph-theoretical terminology and notation not defined here we follow [24] .
Let
be connected. A fault set
is called a g-good-neighbor faulty set if
for every vertex v in
. A g-good-neighbor cut of G is a g-good-neighbor faulty set F such that
is disconnected. The minimum cardinality of g-good-neighbor cuts is said to be the g-good-neighbor connectivity of G, denoted by
. A connected graph G is said to be g-good-neighbor connected if G has a g-good-neighbor cut.
Definition 2.1. A system
is g-good-neighbor t-diagnosable under the PMC model if and only if
is distinguishable for each distinct pair of g-good-neighbor faulty subsets
and
of V with
and
. The g-good-neighbor diagnosability
of G is the maximum value of t such that G is g-good-neighbor t-diagnosable under the PMC model. In particular,
is said to be the diagnosability of G under the PMC model,
is said to be the nature diagnosability of G under the PMC model.
Definition 2.2. A system
is g-good-neighbor t-diagnosable under the MM* model if and only if
is distinguishable for each distinct pair of g-good-neighbor faulty subsets
and
of V with
and
. The g-good-neighbor diagnosability
of G is the maximum value of t such that G is g-good-neighbor t-diagnosable under the MM* model. In particular,
is said to be the diagnosability of G under the MM* model,
is said to be the nature diagnosability of G under the MM* model.
For a given position integer n, let
. The sequence
is called a binary string of length n if
for each
. Let
and
be two distinct binary strings of length n.
Hamming distance between x and y, denoted by
, is the number of r’s for which
for
.
For a binary string
of length
, we call
the r-th bit of u for
, and
the last bit of u, denote sub-sequence
of u by
, i.e.,
. Let
.
Definition 2.3. The exchanged hypercube is an undirected graph
, where
and
are integers. The set of vertices V is
, and the set of edges E is composed of three disjoint types
,
and
:
,
,
.
3. The g-Good-Neighbor Diagnosability of the Exchanged Hypercube under the PMC and the MM* Model
Theorem 3.1. [9] For
and any g with
,
.
Let
and let
. Then
. By the proof of Lemma 3.1 in [9] , we have the following.
Lemma 3.2. Let
be the exchanged hypercube with
.
is defined as above for
. Then
,
, and
is a g-good-neighbor cut of
.
Theorem 3.3. [19] Let
be a g-good-neighbor connected graph, and let H be connected subgraph of G with
such that it contains
as least as possible and
is a minimum g-good-neighbor cut of G, and let
be connected subgraph of G with
such that it contains
as least as possible. If
for each distinct pair of g-good-neighbor faulty subsets
and
of G with
and
, then
under the PMC model.
Theorem 3.4. Let
be the exchanged hypercube with
and any g with
. Then the g-good-neighbor diagnosability of
is
under the PMC model.
Proof. Let
be defined in Lemma 3.2 for
. By the definition of
,
is minimum such that
. Note
. Therefore,
for each distinct pair of g-good-neighbor faulty subsets
and
of
with
and
. By Theorem 3.4,
. On the other hand, by Lemma 3.2,
is a g-good-neighbor cut of
. Since
, by Theorem 3.1,
is a minimum g-good-neighbor cut of
. Note
. By Theorem 3.4,
. Therefore,
. ,
Before discussing the g-good-neighbor diagnosability of the exchanged hypercube under the MM* model, we first give two existing results.
Theorem 3.5. [4] [21] A system
is g-good-neighbor t-diagnosable under the MM* model if and only if for each distinct pair of g-good-neighbor faulty subsets
and
of V with
and
satisfies one of the following conditions. 1) There are two vertices
and there is a vertex
such that
and
. 2) There are two vertices
and there is a vertex
such that
and
. 3) There are two vertices
and there is a vertex
such that
and
.
Theorem 3.6. [19] Let
be a g-good-neighbor connected graph, and let H be connected subgraph of G with
such that it contains
as least as possible, and
is a minimum g-good-neighbor cut of G. Then the g-good-neighbor diagnosability of G is less than or equal to
, i.e.,
under the PMC model and MM* model.
Lemma 3.7. Let
be the exchanged hypercube with
and any g with
. Then the g-good-neighbor diagnosability of the exchanged hypercube
under the MM* model is less than or equal to
, i.e.,
.
Proof. Let
be defined in Lemma 3.2 for
. By the definition of
,
is minimum such that
. By Lemma 3.2,
is a g-good-neighbor cut of
. By Theorems 3.6 and 3.1,
. ,
A component of a graph G is odd according as it has an odd number of vertices. We denote by
the number of odd component of G.
Lemma 3.8. [24] A graph
has a perfect matching if and only if
for all
.
Lemma 3.9. [8] Let G be a graph representation of a system. Then the diagnosability
under the MM* model.
Theorem 3.10. Let
be the exchanged hypercube with
. Then the 0-good-neighbor diagnosability of
under the MM* model is
, i.e.,
.
Proof. By the definition of the g-good-neighbor diagnosability, it is sufficient to show that
is 0-good-neighbor
-diagnosable.
By Theorem 3.5, suppose, on the contrary, that there are two distinct 0-good-neighbor faulty subsets
and
of
with
and
, but the vertex set pair
is not satisfied with any one condition in Theorem 3.5. Without loss of generality, assume that
. Note
. Therefore,
.
Note
has a perfect matching. Let
be the set of isolated vertices in
, and let H be the subgraph induced by the vertex set
. By Lemma 3.8,
. Note
. Therefore,
. Since
and
are two distinct 0-good-neighbor faulty sets, and there is no edge between
and
, we have that
is a 0-good-neighbor cut of
. By Theorem 3.1, we have
. Therefore,
, which contradicts
. Therefore,
is 0-good-neighbor
-diagnosable and
. Combining this with Lemma 3.9, we have
. ,
Theorem 3.11. Let
be the exchanged hypercube with
. Then the 1-good-neighbor diagnosability of
under the MM* model is
, i.e.,
.
Proof. By the definition of 1-good-neighbor diagnosability, it is sufficient to show that
is 1-good-neighbor
-diagnosable.
By Theorem 3.5, suppose, on the contrary, that there are two distinct 1-good-neighbor faulty subsets
and
of
with
and
, but the vertex set pair
is not satisfied with any one condition in Theorem 3.5. Without loss of generality, assume that
. Note
. Therefore,
.
Claim I.
has no isolated vertex.
Suppose, on the contrary, that
has at least one isolated vertex w. Since
is a 1-good neighbor faulty set, there is a vertex
such that u is adjacent to w. Since the vertex set pair
is not satisfied with any one condition in Theorem 3.5, there is at most one vertex
such that u is adjacent to w. Thus, there is just a vertex
such that u is adjacent to w. If
, then
. Since
is a 1-good neighbor faulty set,
has not any isolated vertex; a contradiction. Therefore,
. Similarly, we can deduce that there is just a vertex
such that v is adjacent to w. Let
be the set of isolated vertices in
, and let H be the subgraph induced by the vertex set
. Then for any
, there are
neighbors in
. Note
has a perfect matching. By Lemma 3.8,
. Suppose
. Then
. This is a contradiction to
. So
. Since the vertex set pair
is not satisfied with the condition (1) of Theorem 3.5, and any vertex of
is not isolated in H, we induce that there is no edge between
and
. Thus,
is a vertex cut of
and
, i.e.,
is a 1-good-neighbor cut of
. By Theorem 3.1,
. Because
,
, and neither
nor
is empty, we have
and
. Let
and
. Then for any vertex
, w are adjacent to
and
. Note that there are at most two common neighbors for any pair of vertices in
, it follows that there are at most two isolated vertices in
.
Suppose that there is exactly one isolated vertex v in
. Let
and
be adjacent to v. Then
. Since
contains no triangle, it follows that
;
;
,
and
.
Thus,
. It follows that
, which contradicts
.
Suppose that there are exactly two isolated vertices v and w in
. Let
and
be adjacent to v and w, respectively. Then
. Since
contains no triangle, it follows that
,
,
,
and
.
Thus,
. It follows that
, which contradicts
. The proof of Claim I is complete.
Let
. By Claim I, u has at least one neighbor in
. Since the vertex set pair
is not satisfied with any one condition in Theorem 3.5, by the condition (1) of Theorem 3.5, for any pair of adjacent vertices
, there is no vertex
such that
and
. It follows that u has no neighbor in
. By the arbitrariness of u, there is no edge between
and
. Since
and
is a 1-good-neighbor faulty set,
. Note
. Since both
and
are 1-good-neighbor faulty sets, and there is no edge between
and
,
is a 1-good-neighbor cut of
. By Theorem 3.1,
. Therefore,
, which contradicts
. Therefore,
is 1-good-neighbor
-diagnosable and
. Combining this with Lemma 3.7, we have
. ,
Theorem 3.12. Let
be the exchanged hypercube with
and any g with
. Then the g-good-neighbor diagnosability of the exchanged hypercube
under the MM* model is
, i.e.,
.
Proof. By the definition of the
-good-neighbor diagnosability, it is sufficient to show that
is g-good-neighbor
-diagnosable. By Theorems 3.10 and 3.11, it is sufficient to show that
.
By Theorem 3.5, suppose, on the contrary, that there are two distinct g-good-neighbor faulty subsets
and
of
with
and
, but the vertex set pair
is not satisfied with any one condition in Theorem 3.5. Without loss of generality, assume that
. It is easy to verify
. Therefore,
.
Claim 1.
has no isolated vertex.
Suppose, on the contrary, that
has at least one isolated vertex x. Since
is a g-good neighbor faulty set and
, there are at least two vertices
such that
are adjacent to x. According to the hypothesis, the vertex set pair
is not satisfied with any one condition in Theorem 3.5. By the condition (3) of Theorem 3.5, there are at most one vertex
such that u are adjacent to x. So
, a contradiction to that
is a g-good neighbor faulty set, where
. Thus,
has no isolated vertex.
The proof of Claim 1 is complete.
Let
. By Claim 1,
. Since the vertex set pair
is not satisfied with any one condition in Theorem 3.5, by the condition (1) of Theorem 3.5, for any pair of adjacent vertices
, there is no vertex
such that
and
. It follows that u has no neighbor in
. By the arbitrariness of u, there is no edge between
and
. Since
and
is a g-good-neighbor faulty set,
and
. By the definition of
,
. Since both
and
are g-good-neighbor faulty sets, and there is no edge between
and
,
is a g-good-neighbor cut of
. By Theorem 3.1,
. Therefore,
, which contradicts
. Therefore,
is g-good-neighbor
-diagnosable and
. Combining this with Lemma 3.7, we have
. ,
4. Conclusion
In this paper, we investigate the problem of the diagnosability of the exchanged hypercube
. We show the following. Let
be the exchanged hypercube with
and any g with
. Then the g-good-neighbor diagnosability of
under the PMC model and MM* model is
. The work will help engineers to develop more different measures of the diagnosability based on application environment, network topology, network reliability, and statistics related to fault patterns.
Acknowledgements
This work is supported by the National Natural Science Foundation of China (61772010) and the Science Foundation of Henan Normal University (Xiao 20180529, 20180454).