The Tightly Super 3-Extra Connectivity and Diagnosability of Locally Twisted Cubes ()
1. Introduction
At present, semiconductor technology has been widely applied in various fields of large-scale computer systems. But processors or communication links failures of a multiprocessor system give our live a lot of troubles. How to find out the faulty processors accurately and timely becomes the primary problem when the system is in operation. The diagnosis of the system is the process of identifying the faulty processors from the fault-free ones.
There are two well-known diagnosis models, one is the PMC diagnosis model, introduced by Preparata et al. [1] and the other is the MM model, proposed by Maeng and Malek [2] . In the PMC model, any two neighbor processors can test each other. In the MM model, to diagnose a system, we can compare their responses after a node sends the same task to its two neighbors. Sengupta and Dahbura [3] suggested a further modification of the MM model, called the MM* model, in which each node must test another two neighbors.
In 1996, the g-extra connectivity
of an interconnection network G was introduced by Fàbrega and Fiol [4] . The g-extra connectivity
of an interconnection network G has been widely studied [4] - [13] .
In 2012, Peng et al. [14] proposed a measure for faulty diagnosis of the system, namely, the g-good-neighbor diagnosability, which restrains every fault-free node containing at least g fault-free neighbors. In [14] , they studied the g-good- neighbor diagnosability of the n-dimensional hypercube under the PMC model. In 2016, Wang and Han [15] studied the g-good-neighbor diagnosability of the n-dimensional hypercube under the MM* model. In 2016, Zhang et al. [16] proposed the g-extra diagnosability of the system, which restrains that every component of
has at least
vertices and showed the g-extra diagnosability of hypercubes under the PMC model and MM* model. Ren et al. [17] studied the tightly super 2-extra connectivity and 2-extra diagnosability of locally twisted cubes
. In 2016, Wang et al. [18] studied the 2-extra diagnosability of the bubble-sort star graph
under the PMC model and MM* model. In 2017, Wang and Yang [19] studied the 2-good-neighbor (2- extra) diagnosability of alternating group graph networks under the PMC model and MM* model.
In this paper, we show that
is tightly
super 3-extra con- nected for
and the 3-extra diagnosability of
under the PMC model and MM* model is
for
and
, respectively.
2. Preliminaries
2.1. Notations
A multiprocessor system is modeled as an undirected simple graph
, whose vertices (nodes) represent processors and edges (links) represent com- munication links. Suppose that
is a nonempty vertex subset of V. The in- duced subgraph by
in G, denoted by
, is a graph, whose vertex set is
and whose edge set consists of all the edges of G with both endpoints in
. The degree
of a vertex v in G is the number of edges incident with v. We denote by
the minimum degree of vertices of G. For any vertex v, we define the neighborhood
of v in G to be the set of vertices adjacent to v.
is called a neighbor vertex or a neighbor of v for
. Let
. We denote by
the set
. For neighborhoods and degrees, we will usually omit the subscript for the graph when no confusion arises. A graph G is said to be k-regular if
for any vertex
. A bipartite graph is one whose each edge has one end in subsets of vertex X and one end in subsets of vertex Y; such a partition
is called a bipartition of the graph. A complete bipartite graph is a simple bipartite graph with bipartition
in which each vertex of X is joined to each vertex of Y; if
and
, such a graph is denoted by
. The connectivity
of a connected graph G is the minimum number of vertices whose removal results in a disconnected graph or only one vertex left. Let
and
be two distinct subsets of V, and let the symmetric difference
. For graph-theoretical terminology and notation not defined here we follow [20] .
Let
be a connected graph. A faulty 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 faulty set
is called a g-extra faulty set if every component of
has at least
vertices. A g-extra cut of G is a g-extra faulty set F such that
is dis- connected. The minimum cardinality of g-extra cuts is said to be the g-extra connectivity of G, denoted by
.
Proposition 1. ( [21] ) Let G be a g-extra and g-good-neighbor connected graph. Then
.
Proposition 2. ( [21] ) Let G be a 1-good-neighbor connected graph. Then
.
2.2. Definitions and Propositions
Definition 3. ( [22] [23] [24] [25] ) A system G is said to be t-diagnosable if all faulty processors can be identified without replacement, provided that the number of faults presented does not exceed t. The diagnosability of G is the maximum value of t such that G is t-diagnosable.
For the PMC model and MM* model, we follow [26] . Under the PMC model, to diagnose a system
, two adjacent nodes in G are capable to perform tests on each other. For two adjacent nodes u and v in
, the test performed by u on v is represented by the ordered pair
. The outcome of a test
is 1 (resp. 0) if u evaluate v as faulty (resp. fault-free). We assume that the testing result is reliable (resp. unreliable) if the node u is fault- free(resp. faulty). A test assignment T for G is a collection of tests for every adjacent pair of vertices. The collection of all test results for a test assignment T is called a syndrome. For a given syndrome
, a subset of vertices
is said to be consistent with
if syndrome
can be produced from the situation that, for any
such that
,
if and only if
. Let
denote the set of all syndromes which F is consistent with. Under the PMC model, two distinct sets
and
in
are said to be indistinguishable if
, otherwise,
and
are said to be distinguishable.
Similar to the PMC model, we can define a subset of vertices
is consistent with a given syndrome
and two distinct sets
and
in
are indistinguishable (resp. distinguishable) under the MM* model.
In a system
, a faulty set
is called a g-extra faulty set if every component of
has more than g nodes. G is g-extra t-diagnosable if and only if for each pair of distinct faulty g-extra vertex subsets
such that
,
and
are distinguishable. The g-extra diagnosability of G, denoted by
, is the maximum value of t such that G is g-extra t- diagnosable.
Proposition 4. [18] For any given system G,
if
.
For an integer
, a binary string of length n is denoted by
, where
for any integer
. The n-dimensional locally twisted cube, denoted by
, is an n-regular graph of
vertices and
edges, which can be recursively defined as follows [27] .
Definition 5. ( [27] ) For
, an n-dimensional locally twisted cube, denoted by
, is defined recursively as follows:
1)
is a graph consisting of four nodes labeled with 00, 01, 10 and 11, respectively, connected by four edges {00, 01}, {01, 11}, {11, 10} and {10, 00}.
2) For
,
is built from two disjoint copies of
according to the following steps. Let
denote the graph obtained from one copy of
by prefixing the label of each node with 0. Let
denote the graph obtained from the other copy of
by prefixing the label of each node with 1. Connect each node
of
to the node
of
with an edge, where “+” represents the modulo 2 addition.
The edges whose end vertices in different
are called to be cross- edges. Figures 1-3 show four examples of locally twisted cubes. The locally twisted cube can also be equivalently defined in the following non-recursive fashion.
Definition 6. ( [27] ) For
, the n-dimensional locally twisted cube, denoted by
, is a graph with
as the node set. Two nodes
and
of
are adjacent if and only if either one of the following conditions are satisfied.
1)
and
for some
,
and
for all the remaining bits;
2)
for
,
and
for all the remaining bits.
Proposition 7. ( [28] ) Let
be the locally twisted cube. If two vertices
are adjacent, there is no common neighbor vertex of these two vertices, i.e.,
. If two vertices
are not adjacent, there are at most two common neighbor vertices of these two vertices, i.e.,
.
3. The Connectivity of Locally Twisted Cubes
Lemma 1. ( [27] ) Let
be the locally twisted cube. Then
.
Lemma 2. ( [29] ) Let
be the locally twisted cube, and let
and
. If
is disconnected and
, then
has exactly two components, one is trivial and the other is nontrivial.
Lemma 3. ( [17] ) Let
be the locally twisted cube. Then all cross-edges of
is a perfect matching.
Lemma 4. ( [30] ) Let
be the locally twisted cube. Then
.
Lemma 5. Let
be the locally twisted cube. If
is a 3-path in
and
for
,
.
Proof. We decompose
into
and
. Then
and
are isomorphic to
. Without loss of generality, we have the following cases.
Case 1.
and
.
Since
,
and
are adjacent, by Propo- sition 7,
have no the common neighbor vertex. Similarly,
have no the common neighbor vertex and
have no the common neighbor vertex. Since
,
,
are not adjacent, v is a com- mon neighbor vertex of
,
and x is a neighbor vertex of w, by Lemma 3,
. Similarly,
. Since u and x are not adjacent, by proposition 7,
. Therefore,
.
Case 2.
and
.
Since
are adjacent, by Proposition 7,
. Similarly,
,
. And since
,
,
are not adjacent and v is the common neighbor vertex of u and w, by Lemma 3,
. Since
are not adjacent,
,
, by Lemma 3,
. Since w is the common neighbor vertex of v and x and
are not adjacent, by pro- position 7,
. Therefore,
.
Case 3.
and
.
Since
are adjacent, by Proposition 7,
. Similarly,
,
. Since
,
and u, x are not adjacent, by proposition 7,
. If
, then, by Lemma 3,
. If
, then, by Lemma 3,
. Therefore,
.
Case 4.
.
This case is clear.
In conclusion,
.
Lemma 6. Let
be the locally twisted cube. If
is isomorphic to
for
and
, then
.
Proof. Since
and
is isomorphic to
, we have
,
and
. Since
are not adjacent and u is a common neighbor vertex of v, w, by Proposition 7,
. Similarly,
,
. Therefore,
.
If
is a 4-cycle, then
. Combining this with Lemmas 5 and 6, we have the following corollary.
Corollary 1. Let
be the locally twisted cube and let H be a connected subgraph of
. If
, then
.
Lemma 7. Let
and let
be the locally twisted cube with
. If
,
, where
, then
,
,
is a 3-extra cut of
,
has two components
and
,
, and
.
Proof. According to the definition,
is a 3-path and
. By Lemma 5,
. From Figure 2 and the definition of
, we have that
. Therefore,
. Let
,
.
To prove
has two components and
, we have the following discussion.
Claim 1.
is connected for
.
The proof is by induction on n. For
,
,
. It is easy to see that
is connected (See Figure 2). When
,
,
(See Figure 3). It is clear that
is connected (See Figure 3). We discompose
into
and
. Assume that
, the result holds for
. Then
is con- nected. Note that
and
. By Lemma 1,
is connected. By inductive hypothesis,
is con- nected. Since
, by Lemma 3,
is connected. The proof of Claim 1 is complete.
By Claim 1,
has two components
and
for
. Then
for
. And since
,
is a 3-extra cut of
.
Lemma 8. ( [17] ) Let
be the locally twisted cube. If
, then
satisfies one of the following conditions:
1)
has three components, two of which are isolated vertices;
2)
has two components, one of which is an isolated vertex;
3)
has two components, one of which is a
;
4)
is connected.
Theorem 8. ( [31] ) Let
be the locally twisted cube. Then
for
.
Lemma 9. Let
be the locally twisted cube. If
for
, then
satisfies one of the following conditions:
1)
has four components, three of which are isolated vertices;
2)
has three components, one of which is isolated vertices and one of which is a
;
3)
has three components, two of which are isolated vertices;
4)
has two components, one of which is a path of length two;
5)
has two components, one of which is an isolated vertex;
6)
has two components, one of which is a
;
7)
is connected.
Proof. We decompose
into
and
. Then
and
are isomorphic to
. Suppose that
,
. Without loss of generality, let
. And since
,
,
. Let
be the maximum component of
,
. We consider the following cases.
Case 1.
.
Since
and
,
. By Lemmas 1 and 2, both
and
are connected or has two components, one of which is an isolated vertex. Since
, by Lemma 3,
is connected. Thus,
satisfies one of con- ditions:
1)
has three components, two of which are isolated vertices;
2)
has two components, one of which is an isolated vertex;
3)
has two components, one of which is a
;
4)
is connected.
Case 2.
.
Since
and
,
. By Lemmas 1 and 2,
is connected or has two components, one of which is an isolated vertex. Since
, by Lemma 8,
satisfies one of the following conditions:
1)
has three components, two of which are isolated vertices;
2)
has two components, one of which is an isolated vertex;
3)
has two components, one of which is a
;
4)
is connected.
Then
satisfies one of the conditions (1)-(7).
Case 3.
.
Since
and
,
. By Lemma 1,
is connected.
Suppose that
is connected. Since
, by Lemma 3,
is connected.
Suppose that
is not connected. Let the components in
be
for
and
. If
, by Lemma 3,
. Combining this with
, we have that
is connected. Therefore,
is not a component of
for
. Therefore,
is connected. The following we discuss
is a com- ponent of
with
.
If
, by Lemma 3,
. Combining this with
, there is one
such that
is connected. Thus,
. Since
,
, and
,
satisfies one of the conditions (1)-(7).
Lemma 10. Let
be the locally twisted cube. If
for
, then
satisfies one of the following conditions:
1)
has four components, three of which are isolated vertices;
2)
has three components, one of which is isolated vertices and one of which is a
;
3)
has three components, two of which are isolated vertices;
4)
has two components, one of which is a path of length two;
5)
has two components, one of which is an isolated vertex;
6)
has two components, one of which is a
;
7)
is connected.
Proof. By Lemma 9, the result holds for
. We proceed by induction on n. Assume
and the result holds for
, i.e., if
, then
satisfies one of the con- ditions (1)-(7) in Lemma 10. The following we prove
satisfies one of the conditions (1)-(7).
We decompose
into
and
. Then
and
are isomorphic to
. Suppose that
,
. Without loss of generality, let
. And since
,
,
.
Let
be the maximum component of
,
. We consider the following cases.
Case 1.
.
Since
and
,
. By Lemmas 1 and 2,
is connected or has two components, one of which is an isolated vertex. Since
, by lemma 8,
satisfies one of the following conditions: 1)
has three components, two of which are isolated vertices; 2)
has two components, one of which is an isolated vertex; 3)
has two components, one of which is a
; 4)
is connected. Since
, by Lemma 3,
is connected. Thus,
satisfies one of con- ditions (1)-(7) in Lemma 10.
Case 2.
.
Since
and
,
. By Le- mma 1,
is connected. Since
, according to inductive hypothesis,
satisfies one of the following conditions:
1)
has four components, three of which are isolated vertices;
2)
has three components, one of which is isolated vertices and one of which is a
;
3)
has three components, two of which are isolated vertices;
4)
has two components, one of which is a path of length two;
5)
has two components, one of which is an isolated vertex;
6)
has two components, one of which is a
;
7)
is connected.
Thus,
satisfies one of the conditions (1)-(7) in Lemma 10.
Case 3.
.
Since
and
,
. By Lemma 1,
is connected.
Suppose that
is connected. Since
, by Le- mma 3,
is connected.
Suppose that
is not connected. Let the components in
be
for
and
. If
, by Lemma 3,
. Combining this with
, we have that
is connected. Therefore,
is not a com- ponent of
for
. Therefore,
is connected. The following we discuss
is a component of
with
.
If
, by Lemma 3,
. Combining this with
, there is one
such that
is connected. Thus,
. Since
,
and
,
satisfies one of the conditions (1)-(7).
A connected graph G is super g-extra connected if every minimum g-extra cut F of G isolates one connected subgraph of order
. In addition, if
has two components, one of which is the connected subgraph of order
, then G is tightly
super g-extra connected.
Theorem 9. Let
be the locally twisted cube for
. Then
is tightly
super 3-extra connected.
Proof. By Theorem 8, we know for any minimum 3-extra cut
,
. We decompose
into
and
. Then
and
are isomorphic to
. Suppose that
,
. Without loss of generality, let
. And
since
,
,
.
Let
be the maximum component of
,
. We consider the following cases.
Case 1.
.
Since
and
,
holds.
By Lemmas 1 and 2,
is connected or has two components, one of which is an isolated vertex. Since
, by lemma 8,
satisfies one of the following conditions: 1)
has three components, two of which are isolated vertices; 2)
has two components, one of which is an isolated vertex; 3)
has two com- ponents, one of which is a
; 4)
is connected. Since
, by Lemma 3,
is connected. Then
satisfies one of the following conditions:
1)
has four components, three of which are isolated vertices;
2)
has three components, one of which is isolated vertices and one of which is a
;
3)
has three components, two of which are isolated vertices;
4)
has two components, one of which is a path of length two;
5)
has two components, one of which is an isolated vertex;
6)
has two components, one of which is a
;
7)
is connected.
Thus, in this case, F is not a minimum 3-extra cut of
, a contradiction.
Case 2.
.
Since
and
, we have
. By Lemmas 1 and 2,
is connected or has two components, one of which is an isolated vertex. Since
, by Lemma 10,
satisfies one of the following conditions:
1)
has four components, three of which are isolated vertices;
2)
has three components, one of which is isolated vertices and the other of which is a
;
3)
has three components, two of which are isolated vertices;
4)
has two components, one of which is a path of length two;
5)
has two components, one of which is an isolated vertex;
6)
has two components, one of which is a
;
7)
is connected.
If
satisfies the condition (4), i.e.,
has two com- ponents, one of which is a path of length two, denoted by
,
has two components, one of which is an isolated vertex x, and
,
, then, by Lemma 3,
has one component which is a 3-path or a
. Since
for
,
is connected. Thus,
exactly has two components. Then the other component C satisfies
for
. Otherwise, F is not a minimum 3-extra cut of
, a contradiction.
Case 3.
.
Since
and
,
. By Le- mma 1,
is connected. Since
, by Lemma 10,
satisfies one of the following conditions:
1)
has four components, three of which are isolated vertices;
2)
has three components, one of which is isolated vertices and the other of which is a
;
3)
has three components, two of which are isolated vertices;
4)
has two components, one of which is a path of length two;
5)
has two components, one of which is an isolated vertex;
6)
has two components, one of which is a
;
7)
is connected.
Thus,
satisfies one of the following conditions:
1)
has four components, three of which are isolated vertices;
2)
has three components, one of which is isolated vertices and one of which is a
;
3)
has three components, two of which are isolated vertices;
4)
has two components, one of which is a path of length two;
5)
has two components, one of which is an isolated vertex;
6)
has two components, one of which is a
;
7)
is connected.
In this case, F is not a minimum 3-extra cut of
, a contradiction.
Case 4.
.
Since
and
for
,
. By Lemma 1,
is connected.
If there exists a 3-path P in
, then
. By Corollary 1,
in
. Therefore,
in
. Note that
for
, by Lemma 3, then
is connected. Then
just has two components, one of which is a 3-path.
If there exists a component
in
, then
. By Corollary 1,
in
. Therefore,
in
. Note that
for
, by Lemma 3,
just has two com- ponents, one of which is a
.
If there exists a 4-cycle C in
, then
. By Proposition 7,
, a contradiction to
. Therefore,
has not a 4-cycle.
Case 5.
.
Since
and
,
. By Lemma 1,
is connected.
Suppose that
is connected. Since
, by Le- mma 3,
is connected, a contradiction.
Suppose that
is not connected. Let the components in
be
for
and
. If
, by Lemma 3,
. If
, by Lemma 3,
. Combining this with
, we have that
satisfies one of the following conditions:
1)
has four components, three of which are isolated vertices;
2)
has three components, one of which is isolated vertices and one of which is a
;
3)
has three components, two of which are isolated vertices;
4)
has two components, one of which is a path of length two;
5)
has two components, one of which is an isolated vertex;
6)
has two components, one of which is a
;
7)
is connected.
In this case, F is not a minimum 3-extra cut of
, a contradiction.
4. The 3-Extra Diagnosability of the Locally Twisted Cube under the PMC Model
In this section, we shall show the 3-extra diagnosability of locally twisted cubes under the PMC model.
Theorem 10. ( [16] [22] [26] ) A system
is g-extra t-diagnosable under the PMC model if and only if there is an edge
with
and
for each distinct pair of g-extra faulty sub- sets
and
of V with
and
.
Lemma 11. Let
. Then the 3-extra diagnosability of the locally twisted cube
under the PMC model is less than or equal to
, i.e.,
.
Proof. Let A be defined in Lemma 7, and let
,
. By Lemma 7,
,
,
and
,
is a 3-extra cut of
. Therefore,
and
are 3-extra faulty sets of
with
and
. Since
and
, there is no edge of
between
and
. By Theorem 10, we can deduce that
is not 3-extra
-diagnosable under PMC model. Hence, by the definition of 3-extra diagnosability, we conclude that the 3-extra diagnosability of
is less than
, i.e.,
.
Lemma 12. Let
. Then the 3-extra diagnosability of the locally twisted cube
under the PMC model is more than or equal to
, i.e.,
.
Proof. By the definition of 3-extra diagnosability, it is sufficient to show that
is 3-extra
-diagnosable. By Theorem 10, to prove
is 3- extra
-diagnosable, it is equivalent to prove that there is an edge
with
and
for each distinct pair of 3-extra faulty subsets
and
of
with
and
.
Suppose, by way of contradiction, that there are two distinct 3-extra faulty subsets
and
of
with
and
, but the vertex set pair
is not satisfied with the condition in Theorem 10, i.e., there are no edges between
and
. Without loss of generality, assume that
.
Assume
. Since
, we have that
, a contra- diction. Therefore,
.
The following we discuss the case when
and
.
Since there are no edges between
and
, and
is a 3-extra faulty set,
has two parts
and
. Thus, every component
of
satisfies
and every component
of
satisfies
. Similarly, every component
of
satisfies
when
. Therefore,
is also a 3-extra faulty set. Since there are no edges between
and
,
is also a 3-extra cut. When
,
is also a 3-extra faulty set. Since there are no edges between
and
,
is a 3-extra cut. By Theorem 8,
. Therefore,
, which contradicts with that
. So
is 3-extra
-diagnosable. By the definition of
,
. The proof is complete.
Combining Lemmas 11 and 12, we have the following theorem.
Theorem 11. Let
. Then the 3-extra diagnosability of the locally twisted cubes
under the PMC model is
.
5. The 3-Extra Diagnosability of the Locally Twisted Cube under the MM* Model
Before discussing the 3-extra diagnosability of the locally twisted cube
under the MM* model, we first give an existing result.
Theorem 12 ( [3] [16] [26] ) A system
is g-extra t-diagnosable under the MM* model if and only if for each distinct pair of g-extra faulty sub- sets
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
.
Lemma 13. Let
. Then the 3-extra diagnosability of the locally twisted cube
under the MM* model is less than or equal to
, i.e.,
.
Proof. Let A be defined in Lemma 7, and let
,
. By Lemma 7,
,
,
and
,
is a 3-extra cut of
. Therefore,
and
are 3-extra faulty sets of
with
and
. Since
and
, there is no edge of
between
and
. By Theorem 12, we can deduce that
is not 3-extra
-diagnosable under MM* model. Hence, by the definition of 3-extra diagnosability, we conclude that the 3-extra diagnosability of
is less than
, i.e.,
.
A component of a graph G is odd or even according as it has an odd or even number of vertices. We denote by
the number of odd components of G.
Lemma 14. ( [20] ) A graph
has a perfect matching if and only if
for all
.
Lemma 15. Let
. Then the 3-extra diagnosability of the locally twisted cube
under the MM* model is more than or equal to
, i.e.,
.
Proof. By the definition of the 3-extra diagnosability, it is sufficient to show that
is 3-extra
-diagnosable.
By Theorem 12, suppose, by way of contradiction, that there are two distinct 3-extra faulty subsets
and
of
with
and
, but the vertex set pair
is not satisfied with any one condition in Theorem 12. Without loss of generality, assume that
. Similarly to the discussion on
in Lemma 12, we can deduce
. Therefore, we have the following discussion for
.
Claim 1.
has no isolated vertex.
Suppose, by way of contradiction, that
has at least one isolated vertex w. Since
is a 3-extra faulty set, there is at least one vertex
such that u are adjacent to w. Since the vertex set pair
is not satisfied with any one condition in Theorem 12, by the condition (3) of Theorem 12, there is at most one vertex
such that u is adjacent to w. Therefore, there is just a vertex u is adjacent to w.
Case 1.
.
If
, then
. Since
is a 3-extra faulty set, every com- ponent
of
has
. Thus,
has no isolated vertex.
Case 2.
.
Similarly, since
, by the condition (2) of Theorem 12 and the hypothesis, 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 H be the induced subgraph by the vertex set
. Then for any
, there are
neighbors in
. By Lemmas 14 and 3,
. Assume
. Then
, a contradiction to that
. So
.
The following we discuss the case when
,
and
.
Since the vertex set pair
is not satisfied with the condition (1) of Theorem 12, and there are not isolated vertices in
, we induce that there is no edge between
and
. Note that
. If
, then this is a contradiction to that
is connected. Therefore,
. Thus,
is a vertex cut of
. Since
is a 3-extra faulty set of
, we have that every component
of H has
and every component
of
has
. Since
also is a 3-extra faulty set of
, we have that every component
of
has
. Note that
has two parts: H and
. Let
. If
, then
has two neighbors
and
. Then
and
. Thus,
is a 3-extra cut of
. By Theorem 8,
. Since
,
. Since
, we have
. Then
and
. Similarly,
,
. By Lemma 9, the locally twisted cube
is tightly
super 3-extra connected, i.e.,
has two components, one of which is a subgraph of or- der 4. Noted that
.
, a contradiction to
. Therefore,
has no isolated vertex when
,
and
. The proof of Claim 1 is complete.
Let
. By Claim 1, u has at least one neighbor vertex in
. Since the vertex set pair
is not satisfied with any one condition in Theorem 12, by the condition (1) of Theorem 12, for any pair of adjacent vertices
, there is no vertex
such that
and
. It follows that u has no neighbor vertex in
. By the arbitrariness of u, there is no edge between
and
. Since
and
is a 3-extra faulty set,
and
. Since
also is 3-extra faulty sets,
and
. Then
is a 3- extra cut of
. By Theorem 8, we have
. Therefore,
, which contradicts
. Therefore,
is 3-extra
-diagnosable and
. The proof is complete.
Combining Lemmas 13 and 15, we have the following theorem.
Theorem 13. Let
. Then the 3-extra diagnosability of the locally twisted cube
under the MM* model is
.
Acknowledgements
This work is supported by the National Science Foundation of China (61370001).