The Tightly Super 3-Extra Connectivity and Diagnosability of Locally Twisted Cubes

Abstract

Diagnosability of a multiprocessor system G is one important measure of the reliability of interconnection networks. In 2016, Zhang et al. proposed the g-extra diagnosability of G, which restrains that every component of G – S has at least (g + 1) vertices. The locally twisted cube LTQn is applied widely. In this paper, we show that LTQn is tightly (4n – 9) super 3-extra connected for n 6 and the 3-extra diagnosability of LTQn under the PMC model and MM* model is 4n - 6 for n 5 and n 7, respectively.

Share and Cite:

Wang, M. , Ren, Y. , Lin, Y. and Wang, S. (2017) The Tightly Super 3-Extra Connectivity and Diagnosability of Locally Twisted Cubes. American Journal of Computational Mathematics, 7, 127-144. doi: 10.4236/ajcm.2017.72011.

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 κ ˜ ( g ) ( G ) of an interconnection network G was introduced by Fàbrega and Fiol [4] . The g-extra connectivity κ ˜ ( g ) ( G ) 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 G S has at least ( g + 1 ) 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 L T Q n . In 2016, Wang et al. [18] studied the 2-extra diagnosability of the bubble-sort star graph B S n 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 L T Q n is tightly ( 4 n 9 ) super 3-extra con- nected for n 6 and the 3-extra diagnosability of L T Q n under the PMC model and MM* model is 4 n 6 for n 5 and n 7 , respectively.

2. Preliminaries

2.1. Notations

A multiprocessor system is modeled as an undirected simple graph G = ( V , E ) , whose vertices (nodes) represent processors and edges (links) represent com- munication links. Suppose that V is a nonempty vertex subset of V. The in- duced subgraph by V in G, denoted by G [ V ] , is a graph, whose vertex set is V and whose edge set consists of all the edges of G with both endpoints in V . The degree d G ( v ) of a vertex v in G is the number of edges incident with v. We denote by δ ( G ) the minimum degree of vertices of G. For any vertex v, we define the neighborhood N G ( v ) of v in G to be the set of vertices adjacent to v. u is called a neighbor vertex or a neighbor of v for u N G ( v ) . Let S V ( G ) . We denote by N G ( S ) the set v S N G ( v ) \ S . 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 d G ( v ) = k for any vertex v V . 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 ( X , Y ) is called a bipartition of the graph. A complete bipartite graph is a simple bipartite graph with bipartition ( X , Y ) in which each vertex of X is joined to each vertex of Y; if | X | = m and | Y | = n , such a graph is denoted by K m , n . The connectivity κ ( G ) of a connected graph G is the minimum number of vertices whose removal results in a disconnected graph or only one vertex left. Let F 1 and F 2 be two distinct subsets of V, and let the symmetric difference F 1 Δ F 2 = ( F 1 \ F 2 ) ( F 2 \ F 1 ) . For graph-theoretical terminology and notation not defined here we follow [20] .

Let G = ( V , E ) be a connected graph. A faulty set F V is called a g- good-neighbor faulty set if | N ( v ) ( V \ F ) | g for every vertex v in V \ F . A g-good-neighbor cut of G is a g-good-neighbor faulty set F such that G F is disconnected. The minimum cardinality of g-good-neighbor cuts is said to be the g-good-neighbor connectivity of G, denoted by κ ( g ) ( G ) . A faulty set F V is called a g-extra faulty set if every component of G F has at least ( g + 1 ) vertices. A g-extra cut of G is a g-extra faulty set F such that G F is dis- connected. The minimum cardinality of g-extra cuts is said to be the g-extra connectivity of G, denoted by κ ˜ ( g ) ( G ) .

Proposition 1. ( [21] ) Let G be a g-extra and g-good-neighbor connected graph. Then κ ˜ ( g ) ( G ) κ ( g ) ( G ) .

Proposition 2. ( [21] ) Let G be a 1-good-neighbor connected graph. Then κ ( 1 ) ( G ) = κ ˜ ( 1 ) ( G ) .

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 G = ( V ( G ) , E ( G ) ) , two adjacent nodes in G are capable to perform tests on each other. For two adjacent nodes u and v in V ( G ) , the test performed by u on v is represented by the ordered pair ( u , v ) . The outcome of a test ( u , v ) 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 F V ( G ) is said to be consistent with σ if syndrome σ can be produced from the situation that, for any ( u , v ) L such that u V \ F , σ ( u , v ) = 1 if and only if v F . Let σ ( F ) denote the set of all syndromes which F is consistent with. Under the PMC model, two distinct sets F 1 and F 2 in V ( G ) are said to be indistinguishable if σ ( F 1 ) σ ( F 2 ) , otherwise, F 1 and F 2 are said to be distinguishable.

Similar to the PMC model, we can define a subset of vertices F V ( G ) is consistent with a given syndrome σ * and two distinct sets F 1 and F 2 in V ( G ) are indistinguishable (resp. distinguishable) under the MM* model.

In a system G = ( V , E ) , a faulty set F V is called a g-extra faulty set if every component of G F 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 F 1 , F 2 V ( G ) such that | F i | t , F 1 and F 2 are distinguishable. The g-extra diagnosability of G, denoted by t ˜ g ( G ) , is the maximum value of t such that G is g-extra t- diagnosable.

Proposition 4. [18] For any given system G, t ˜ g ( G ) t ˜ g ( G ) if g g .

For an integer n 1 , a binary string of length n is denoted by u 1 u 2 u n , where u i { 0,1 } for any integer i { 1,2, , n } . The n-dimensional locally twisted cube, denoted by L T Q n , is an n-regular graph of 2 n vertices and n 2 n 1 edges, which can be recursively defined as follows [27] .

Definition 5. ( [27] ) For n 2 , an n-dimensional locally twisted cube, denoted by L T Q n , is defined recursively as follows:

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

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

The edges whose end vertices in different i L T Q n 1 s 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 n 2 , the n-dimensional locally twisted cube, denoted by L T Q n , is a graph with { 0,1 } n as the node set. Two nodes u 1 u 2 u n and v 1 v 2 v n of L T Q n are adjacent if and only if either one of the following conditions are satisfied.

1) u i = v i ¯ and u i + 1 = ( v i + 1 + v n ) ( m o d 2 ) for some 1 i n 2 , n 3 and u j = v j for all the remaining bits;

Figure 1. LTQ2 and LTQ3.

Figure 2. LTQ4.

Figure 3. LTQ5.

2) u i = v i ¯ for i { n 1, n } , n 2 and u j = v j for all the remaining bits.

Proposition 7. ( [28] ) Let L T Q n be the locally twisted cube. If two vertices u , v are adjacent, there is no common neighbor vertex of these two vertices, i.e., | N ( u ) N ( v ) | = 0 . If two vertices u , v are not adjacent, there are at most two common neighbor vertices of these two vertices, i.e., | N ( u ) N ( v ) | 2 .

3. The Connectivity of Locally Twisted Cubes

Lemma 1. ( [27] ) Let L T Q n be the locally twisted cube. Then κ ( L T Q n ) = n .

Lemma 2. ( [29] ) Let L T Q n be the locally twisted cube, and let S V ( L T Q n ) and n 3 . If L T Q n S is disconnected and n | S | 2 n 3 , then L T Q n S has exactly two components, one is trivial and the other is nontrivial.

Lemma 3. ( [17] ) Let L T Q n be the locally twisted cube. Then all cross-edges of L T Q n is a perfect matching.

Lemma 4. ( [30] ) Let L T Q n be the locally twisted cube. Then κ ( 2 ) ( L T Q n ) = 4 n 8 .

Lemma 5. Let L T Q n be the locally twisted cube. If P = u v w x is a 3-path in L T Q n and u x E ( L T Q n ) for n 3 , | N ( V ( P ) ) | 4 n 9 .

Proof. We decompose L T Q n into 0 L T Q n 1 and 1 L T Q n 1 . Then 0 L T Q n 1 and 1 L T Q n 1 are isomorphic to L T Q n 1 . Without loss of generality, we have the following cases.

Case 1. u , x V ( 0 L T Q n 1 ) and v , w V ( 1 L T Q n 1 ) .

Since u V ( 0 L T Q n 1 ) , v V ( 1 L T Q n 1 ) and u , v are adjacent, by Propo- sition 7, u , v have no the common neighbor vertex. Similarly, x , w have no the common neighbor vertex and v , w have no the common neighbor vertex. Since u V ( 0 L T Q n 1 ) , w V ( 1 L T Q n 1 ) , u , w are not adjacent, v is a com- mon neighbor vertex of u , w , x V ( 0 L T Q n 1 ) and x is a neighbor vertex of w, by Lemma 3, | ( N ( u ) N ( w ) ) \ { v } | = 0 . Similarly, | ( N ( x ) N ( v ) ) \ { w } | = 0 . Since u and x are not adjacent, by proposition 7, | N ( u ) N ( x ) | 2 . Therefore, | N ( V ( P ) ) | 2 ( n 1 ) + 2 ( n 2 ) 2 = 4 n 8 .

Case 2. u V ( 0 L T Q n 1 ) and v , w , x V ( 1 L T Q n 1 ) .

Since u , v are adjacent, by Proposition 7, | N ( u ) N ( v ) | = 0 . Similarly, | N ( v ) N ( w ) | = 0 , | N ( x ) N ( w ) | = 0 . And since u V ( 0 L T Q n 1 ) , w V ( 1 L T Q n 1 ) , u , w are not adjacent and v is the common neighbor vertex of u and w, by Lemma 3, | ( N ( u ) N ( w ) ) \ { v } | 1 . Since u , x are not adjacent, u V ( 0 L T Q n 1 ) , x V ( 1 L T Q n 1 ) , by Lemma 3, | N ( u ) N ( x ) | 1 . Since w is the common neighbor vertex of v and x and v , x are not adjacent, by pro- position 7, | ( N ( v ) N ( x ) ) \ { w } | 1 . Therefore, | N ( P ) | 2 ( n 1 ) + 2 ( n 2 ) 3 = 4 n 9 .

Case 3. u , v V ( 0 L T Q n 1 ) and w , x V ( 1 L T Q n 1 ) .

Since u , v are adjacent, by Proposition 7, | N ( u ) N ( v ) | = 0 . Similarly, | N ( u ) N ( w ) | = 0 , | N ( w ) N ( x ) | = 0 . Since u V ( 0 L T Q n 1 ) , x V ( 1 L T Q n 1 ) and u, x are not adjacent, by proposition 7, | N ( u ) N ( x ) | 2 . If | ( N ( u ) N ( w ) ) \ { v } | = 1 , then, by Lemma 3, | N ( u ) N ( x ) | 1 . If | ( N ( u ) N ( w ) ) \ { v } | = 0 , then, by Lemma 3, | N ( u ) N ( x ) | 2 . Therefore, | N ( V ( P ) ) | 2 ( n 1 ) + 2 ( n 2 ) 2 = 4 n 8 .

Case 4. u , v , w , x V ( 1 L T Q n 1 ) .

This case is clear.

In conclusion, | N ( V ( P ) ) | 4 n 9 .

Lemma 6. Let L T Q n be the locally twisted cube. If L T Q n [ { u , v , w , x } ] is isomorphic to K 1,3 for n 3 and d ( u ) = 3 , then | N ( V ( L T Q n [ { u , v , w , x } ] ) ) | 4 n 9 .

Proof. Since d ( u ) = 3 and L T Q n [ { u , v , w , x } ] is isomorphic to K 1,3 , we have d ( v ) = 1 , d ( w ) = 1 and d ( x ) = 1 . Since v , w are not adjacent and u is a common neighbor vertex of v, w, by Proposition 7, | ( N ( v ) N ( w ) ) \ { u } | 1 . Similarly, | ( N ( v ) N ( x ) ) \ { u } | 1 , | ( N ( w ) N ( x ) ) \ { u } | 1 . Therefore, | N ( V ( L T Q n [ { u , v , w , x } ] ) ) | 3 ( n 1 ) + ( n 3 ) 3 = 4 n 9 .

If L T Q n [ { u , v , w , x } ] is a 4-cycle, then | N ( V ( L T Q n [ { u , v , w , x } ] ) ) | = 4 n 8 . Combining this with Lemmas 5 and 6, we have the following corollary.

Corollary 1. Let L T Q n be the locally twisted cube and let H be a connected subgraph of L T Q n . If | V ( H ) | 4 , then | N ( V ( H ) ) | 4 n 9 .

Lemma 7. Let A = { 0 0001,0 0111,0 0101,0 0100 } and let L T Q n be the locally twisted cube with n 4 . If F 1 = N L T Q n ( A ) , F 2 = F 1 A , where n 4 , then | F 1 | = 4 n 9 , | F 2 | = 4 n 5 , F 1 is a 3-extra cut of L T Q n , L T Q n F 1 has two components L T Q n F 2 and L T Q n [ A ] , | V ( L T Q n F 2 ) | 4 , and | A | 4 .

Proof. According to the definition, L T Q n [ A ] is a 3-path and | A | = 4 . By Lemma 5, | F 1 | 4 n 9 . From Figure 2 and the definition of L T Q n , we have that | F 1 | = 2 ( n 3 ) + 2 ( n 2 ) 3 + 4 = 4 n 9 . Therefore, | F 2 | = | F 1 | + | A | = ( 4 n 9 ) + 4 = 4 n 5 . Let F 2 i = V ( i L T Q n 1 ) F 2 , i { 0,1 } .

To prove L T Q n F 2 has two components and | V ( L T Q n F 2 ) | 4 , we have the following discussion.

Claim 1. L T Q n F 2 is connected for n 4 .

The proof is by induction on n. For n = 4 , A = { 0001 , 0111 , 0101 , 0100 } , F 1 = { 0000 , 0011 , 0110 , 1001 , 1011 , 1101 , 1100 } . It is easy to see that L T Q 4 F 2 is connected (See Figure 2). When n = 5 , A = { 00001 , 00111 , 00101 , 00100 } ,

F 2 1 = { 11001 , 11110 , 11111 , 10100 } (See Figure 3). It is clear that 1 L T Q n 1 F 2 1 is connected (See Figure 3). We discompose L T Q n into 0 L T Q n 1 and 1 L T Q n 1 . Assume that n 6 , the result holds for L T Q n 1 . Then 0 L T Q n 1 F 2 0 is con- nected. Note that A V ( 0 L T Q n 1 ) and | N ( A ) V ( 1 L T Q n 1 ) | = 4 . By Lemma 1, 1 L T Q n 1 F 2 1 is connected. By inductive hypothesis, 0 L T Q n 1 F 2 0 is con- nected. Since 2 n 1 > 4 n 5 , by Lemma 3, L T Q n F 2 is connected. The proof of Claim 1 is complete.

By Claim 1, L T Q n F 1 has two components L T Q n F 2 and L T Q n [ A ] for n 4 . Then | V ( L T Q n F 2 ) | = 2 n ( 4 n 5 ) 4 for n 4 . And since | A | = 4 , F 1 is a 3-extra cut of L T Q n .

Lemma 8. ( [17] ) Let L T Q n ( n 4 ) be the locally twisted cube. If | F | 3 n 6 , then L T Q n F satisfies one of the following conditions:

1) L T Q n F has three components, two of which are isolated vertices;

2) L T Q n F has two components, one of which is an isolated vertex;

3) L T Q n F has two components, one of which is a K 2 ;

4) L T Q n F is connected.

Theorem 8. ( [31] ) Let L T Q n be the locally twisted cube. Then κ ˜ ( 3 ) ( L T Q n ) = 4 n 9 for n 4 .

Lemma 9. Let L T Q n be the locally twisted cube. If | F | = 10 for n = 5 , then L T Q 5 F satisfies one of the following conditions:

1) L T Q 5 F has four components, three of which are isolated vertices;

2) L T Q 5 F has three components, one of which is isolated vertices and one of which is a K 2 ;

3) L T Q 5 F has three components, two of which are isolated vertices;

4) L T Q 5 F has two components, one of which is a path of length two;

5) L T Q 5 F has two components, one of which is an isolated vertex;

6) L T Q 5 F has two components, one of which is a K 2 ;

7) L T Q 5 F is connected.

Proof. We decompose L T Q 5 into 0 L T Q 4 and 1 L T Q 4 . Then 0 L T Q 4 and 1 L T Q 4 are isomorphic to L T Q 4 . Suppose that F i = F V ( i L T Q 4 ) , i { 0,1 } . Without loss of generality, let | F 0 | | F 1 | . And since | F | = 10 , 5 | F 0 | 10 , 0 | F 1 | 5 . Let C i be the maximum component of i L T Q 4 F i , i { 0,1 } . We consider the following cases.

Case 1. | F 0 | = 5 .

Since | F 0 | = 5 and | F | = 10 , | F 1 | = 10 5 = 5 . By Lemmas 1 and 2, both 0 L T Q 4 F 0 and 1 L T Q 4 F 1 are connected or has two components, one of which is an isolated vertex. Since 2 5 1 6 2 1 , by Lemma 3, L T Q n [ V ( C 0 ) V ( C 1 ) ] is connected. Thus, L T Q 5 F satisfies one of con- ditions:

1) L T Q 5 F has three components, two of which are isolated vertices;

2) L T Q 5 F has two components, one of which is an isolated vertex;

3) L T Q 5 F has two components, one of which is a K 2 ;

4) L T Q 5 F is connected.

Case 2. | F 0 | = 6 .

Since | F 0 | = 6 and | F | = 10 , | F 1 | = 10 6 = 4 . By Lemmas 1 and 2, 1 L T Q 4 F 1 is connected or has two components, one of which is an isolated vertex. Since | F 0 | = 6 , by Lemma 8, 0 L T Q 4 F 0 satisfies one of the following conditions:

1) 0 L T Q 4 F 0 has three components, two of which are isolated vertices;

2) 0 L T Q 4 F 0 has two components, one of which is an isolated vertex;

3) 0 L T Q 4 F 0 has two components, one of which is a K 2 ;

4) 0 L T Q 4 F 0 is connected.

Then L T Q 5 F satisfies one of the conditions (1)-(7).

Case 3. | F 0 | 7 .

Since | F 0 | 7 and | F | = 10 , | F 1 | 10 7 = 3 . By Lemma 1, 1 L T Q 4 F 1 is connected.

Suppose that 0 L T Q 4 F 0 is connected. Since 2 5 1 10 1 , by Lemma 3, L T Q n F is connected.

Suppose that 0 L T Q 4 F 0 is not connected. Let the components in 0 L T Q 4 F 0 be G 1 , G 2 , , G k for k 2 and | V ( G 1 ) | | V ( G 2 ) | | V ( G k ) | . If | V ( G r ) | 4 ( 1 r k 1 ) , by Lemma 3, | N ( V ( G r ) ) V ( 1 L T Q 4 ) | 4 . Combining this with | F 1 | 3 , we have that L T Q 5 [ V ( G r ) V ( 1 L T Q 4 F 1 ) ] is connected. Therefore, G r is not a component of L T Q 5 F for | V ( G r ) | 4 . Therefore, L T Q 5 F is connected. The following we discuss G r is a com- ponent of L T Q 5 F with | V ( G r ) | 3 ( 1 r k 1 ) .

If k = 5 , by Lemma 3, | N ( V ( G 1 ) ) N ( V ( G 2 ) ) N ( V ( G k 1 ) ) V ( 1 L T Q 4 ) | 4 . Combining this with | F 1 | 3 , there is one G r ( 1 r k 1 ) such that L T Q 5 [ V ( G r ) V ( 1 L T Q 4 F 1 ) ] is connected. Thus, k 4 . Since | F 1 | = 3 , k 4 , and | V ( G r ) | 3 ( 1 r k 1 ) , L T Q 5 F satisfies one of the conditions (1)-(7).

Lemma 10. Let L T Q n be the locally twisted cube. If 3 n 5 | F | 4 n 10 for n 5 , then L T Q n F satisfies one of the following conditions:

1) L T Q n F has four components, three of which are isolated vertices;

2) L T Q n F has three components, one of which is isolated vertices and one of which is a K 2 ;

3) L T Q n F has three components, two of which are isolated vertices;

4) L T Q n F has two components, one of which is a path of length two;

5) L T Q n F has two components, one of which is an isolated vertex;

6) L T Q n F has two components, one of which is a K 2 ;

7) L T Q n F is connected.

Proof. By Lemma 9, the result holds for n = 5 . We proceed by induction on n. Assume n 6 and the result holds for L T Q n 1 , i.e., if 3 n 5 | F | 4 ( n 1 ) 10 = 4 n 14 , then L T Q n 1 F satisfies one of the con- ditions (1)-(7) in Lemma 10. The following we prove L T Q n F satisfies one of the conditions (1)-(7).

We decompose L T Q n into 0 L T Q n 1 and 1 L T Q n 1 . Then 0 L T Q n 1 and 1 L T Q n 1 are isomorphic to L T Q n 1 . Suppose that F i = F V ( i L T Q n 1 ) , i { 0,1 } . Without loss of generality, let | F 0 | | F 1 | . And since

3 n 5 | F | 4 n 10 , n 3 n 5 2 | F 0 | 4 n 10 , 0 | F 1 | 4 n 10 2 2 n 5 .

Let C i be the maximum component of i L T Q n 1 F i , i { 0,1 } . We consider the following cases.

Case 1. n | F 0 | 3 ( n 1 ) 6 = 3 n 9 .

Since | F 0 | | F 1 | and | F | 4 n 10 ,

( 4 n 10 ) ( 3 n 9 ) = n 1 | F 1 | 4 n 10 2 = 2 n 5 . By Lemmas 1 and 2,

1 L T Q n 1 F 1 is connected or has two components, one of which is an isolated vertex. Since n | F 0 | 3 ( n 1 ) 6 = 3 n 9 , by lemma 8, 0 L T Q n 1 F 0 satisfies one of the following conditions: 1) 0 L T Q n 1 F 0 has three components, two of which are isolated vertices; 2) 0 L T Q n 1 F 0 has two components, one of which is an isolated vertex; 3) 0 L T Q n 1 F 0 has two components, one of which is a K 2 ; 4) 0 L T Q n 1 F 0 is connected. Since 2 n 1 ( 4 n 10 ) 3 1 , by Lemma 3, L T Q n [ V ( C 0 ) V ( C 1 ) ] is connected. Thus, L T Q n F satisfies one of con- ditions (1)-(7) in Lemma 10.

Case 2. 3 n 8 | F 0 | 4 n 14 .

Since | F 0 | | F 1 | and | F | 4 n 10 , | F 1 | ( 4 n 10 ) ( 3 n 8 ) = n 2 . By Le- mma 1, 1 L T Q n 1 F 1 is connected. Since 3 n 8 | F 0 | 4 n 14 , according to inductive hypothesis, 0 L T Q n 1 F 0 satisfies one of the following conditions:

1) 0 L T Q n 1 F 0 has four components, three of which are isolated vertices;

2) 0 L T Q n 1 F 0 has three components, one of which is isolated vertices and one of which is a K 2 ;

3) 0 L T Q n 1 F 0 has three components, two of which are isolated vertices;

4) 0 L T Q n 1 F 0 has two components, one of which is a path of length two;

5) 0 L T Q n 1 F 0 has two components, one of which is an isolated vertex;

6) 0 L T Q n 1 F 0 has two components, one of which is a K 2 ;

7) 0 L T Q n 1 F 0 is connected.

Thus, L T Q n F satisfies one of the conditions (1)-(7) in Lemma 10.

Case 3. 4 n 13 | F 0 | 4 n 10 .

Since 4 n 13 | F 0 | 4 n 10 and | F | 4 n 10 , | F 1 | ( 4 n 10 ) ( 4 n 13 ) = 3 . By Lemma 1, 1 L T Q n 1 F 1 is connected.

Suppose that 0 L T Q n 1 F 0 is connected. Since 2 n 1 ( 4 n 10 ) 1 , by Le- mma 3, L T Q n F is connected.

Suppose that 0 L T Q n 1 F 0 is not connected. Let the components in

0 L T Q n 1 F 0 be G 1 , G 2 , , G k for k 2 and | V ( G 1 ) | | V ( G 2 ) | | V ( G k ) | . If | V ( G r ) | 4 ( 1 r k 1 ) , by Lemma 3, | N ( V ( G r ) ) V ( 1 L T Q n 1 ) | 4 . Combining this with | F 1 | ( 4 n 10 ) ( 4 n 13 ) = 3 , we have that L T Q n [ V ( G r ) V ( 1 L T Q n 1 F 1 ) ] is connected. Therefore, G r is not a com- ponent of L T Q n F for | V ( G r ) | 4 . Therefore, L T Q n F is connected. The following we discuss G r is a component of L T Q n F with | V ( G r ) | 3 ( 1 r k 1 ) .

If k = 5 , by Lemma 3, | N ( V ( G 1 ) ) N ( V ( G 2 ) ) N ( V ( G k 1 ) ) V ( 1 L T Q n 1 ) | 4 . Combining this with | F 1 | 3 , there is one G r ( 1 r k 1 ) such that L T Q n [ V ( G r ) V ( 1 L T Q n 1 F 1 ) ] is connected. Thus, k 4 . Since | F 1 | 3 , | V ( G r ) | 3 ( 1 r k 1 ) and k 4 , L T Q n F 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 g + 1 . In addition, if G F has two components, one of which is the connected subgraph of order g + 1 , then G is tightly | F | super g-extra connected.

Theorem 9. Let L T Q n be the locally twisted cube for n 6 . Then L T Q n is tightly ( 4 n 9 ) super 3-extra connected.

Proof. By Theorem 8, we know for any minimum 3-extra cut F V ( L T Q n ) , | F | = 4 n 9 . We decompose L T Q n into 0 L T Q n 1 and 1 L T Q n 1 . Then 0 L T Q n 1 and 1 L T Q n 1 are isomorphic to L T Q n 1 . Suppose that

F i = F V ( i L T Q n 1 ) , i { 0,1 } . Without loss of generality, let | F 0 | | F 1 | . And

since | F | = 4 n 9 , 2 n 4 4 n 9 2 | F 0 | 4 n 9 , 0 | F 1 | 4 n 9 2 2 n 5 .

Let C i be the maximum component of i L T Q n 1 F i , i { 0,1 } . We consider the following cases.

Case 1. 2 n 4 | F 0 | 3 ( n 1 ) 6 = 3 n 9 .

Since | F 0 | | F 1 | and | F | = 4 n 9 , | F 1 | 2 n 5 holds.

By Lemmas 1 and 2, 1 L T Q n 1 F 1 is connected or has two components, one of which is an isolated vertex. Since 2 n 4 | F 0 | 3 ( n 1 ) 6 = 3 n 9 , by lemma 8, 0 L T Q n 1 F 0 satisfies one of the following conditions: 1) 0 L T Q n 1 F 0 has three components, two of which are isolated vertices; 2) 0 L T Q n 1 F 0 has two components, one of which is an isolated vertex; 3) 0 L T Q n 1 F 0 has two com- ponents, one of which is a K 2 ; 4) 0 L T Q n 1 F 0 is connected. Since 2 n 1 ( 4 n 9 ) 3 1 , by Lemma 3, L T Q n [ V ( C 0 ) V ( C 1 ) ] is connected. Then L T Q n F satisfies one of the following conditions:

1) L T Q n F has four components, three of which are isolated vertices;

2) L T Q n F has three components, one of which is isolated vertices and one of which is a K 2 ;

3) L T Q n F has three components, two of which are isolated vertices;

4) L T Q n F has two components, one of which is a path of length two;

5) L T Q n F has two components, one of which is an isolated vertex;

6) L T Q n F has two components, one of which is a K 2 ;

7) L T Q n F is connected.

Thus, in this case, F is not a minimum 3-extra cut of L T Q n , a contradiction.

Case 2. | F 0 | = 3 n 8 .

Since | F 0 | = 3 n 8 and | F | = 4 n 9 , we have | F 1 | = ( 4 n 9 ) ( 3 n 8 ) = n 1 . By Lemmas 1 and 2, 1 L T Q n 1 F 1 is connected or has two components, one of which is an isolated vertex. Since | F 0 | = 3 n 8 , by Lemma 10, 0 L T Q n 1 F 0 satisfies one of the following conditions:

1) 0 L T Q n 1 F 0 has four components, three of which are isolated vertices;

2) 0 L T Q n 1 F 0 has three components, one of which is isolated vertices and the other of which is a K 2 ;

3) 0 L T Q n 1 F 0 has three components, two of which are isolated vertices;

4) 0 L T Q n 1 F 0 has two components, one of which is a path of length two;

5) 0 L T Q n 1 F 0 has two components, one of which is an isolated vertex;

6) 0 L T Q n 1 F 0 has two components, one of which is a K 2 ;

7) 0 L T Q n 1 F 0 is connected.

If 0 L T Q n 1 F 0 satisfies the condition (4), i.e., 0 L T Q n 1 F 0 has two com- ponents, one of which is a path of length two, denoted by P = u v w , 1 L T Q n 1 F 1 has two components, one of which is an isolated vertex x, and | N ( x ) V ( P ) | = 1 , ( N ( V ( P ) ) V ( 1 L T Q n 1 ) ) \ { x } F 1 , then, by Lemma 3, L T Q n F has one component which is a 3-path or a K 1,3 . Since 2 n 1 ( 4 n 9 ) 3 1 for n 6 , L T Q n [ C 0 C 1 ] is connected. Thus, L T Q n F exactly has two components. Then the other component C satisfies | C | = 2 n ( 4 n 9 ) 4 > 4 for n 6 . Otherwise, F is not a minimum 3-extra cut of L T Q n , a contradiction.

Case 3. 3 n 7 | F 0 | 4 n 14 .

Since | F 0 | | F 1 | and | F | 4 n 9 , | F 1 | ( 4 n 9 ) ( 3 n 7 ) = n 2 . By Le- mma 1, 1 L T Q n 1 F 1 is connected. Since 3 n 7 | F 0 | 4 n 14 , by Lemma 10, 0 L T Q n 1 F 0 satisfies one of the following conditions:

1) 0 L T Q n 1 F 0 has four components, three of which are isolated vertices;

2) 0 L T Q n 1 F 0 has three components, one of which is isolated vertices and the other of which is a K 2 ;

3) 0 L T Q n 1 F 0 has three components, two of which are isolated vertices;

4) 0 L T Q n 1 F 0 has two components, one of which is a path of length two;

5) 0 L T Q n 1 F 0 has two components, one of which is an isolated vertex;

6) 0 L T Q n 1 F 0 has two components, one of which is a K 2 ;

7) 0 L T Q n 1 F 0 is connected.

Thus, L T Q n F satisfies one of the following conditions:

1) L T Q n F has four components, three of which are isolated vertices;

2) L T Q n F has three components, one of which is isolated vertices and one of which is a K 2 ;

3) L T Q n F has three components, two of which are isolated vertices;

4) L T Q n F has two components, one of which is a path of length two;

5) L T Q n F has two components, one of which is an isolated vertex;

6) L T Q n F has two components, one of which is a K 2 ;

7) L T Q n F is connected.

In this case, F is not a minimum 3-extra cut of L T Q n , a contradiction.

Case 4. | F 0 | = 4 n 13 .

Since | F 0 | = 4 n 13 and | F | = 4 n 9 for n 6 , | F 1 | = ( 4 n 9 ) ( 4 n 13 ) = 4 . By Lemma 1, 1 L T Q n 1 F 1 is connected.

If there exists a 3-path P in 0 L T Q n 1 F 0 , then N ( V ( P ) ) V ( 0 L T Q n 1 ) F 0 . By Corollary 1, | N ( V ( P ) ) | 4 n 13 = | F 0 | in 0 L T Q n 1 F 0 . Therefore, N ( V ( P ) ) = F 0 in 0 L T Q n 1 F 0 . Note that 2 n 1 ( 4 n 9 ) 4 1 for n 6 , by Lemma 3, then L T Q n [ V ( C 0 ) V ( C 1 ) ] is connected. Then L T Q n F just has two components, one of which is a 3-path.

If there exists a component K 1,3 in 0 L T Q n 1 F 0 , then N 0 L T Q n 1 ( V ( K 1,3 ) ) F 0 . By Corollary 1, | N ( V ( K 1 , 3 ) ) | 4 n 13 = | F 0 | in 0 L T Q n 1 F 0 . Therefore, N ( V ( K 1 , 3 ) ) = F 0 in 0 L T Q n 1 F 0 . Note that 2 n 1 ( 4 n 9 ) 4 1 for n 6 , by Lemma 3, L T Q n F just has two com- ponents, one of which is a K 1,3 .

If there exists a 4-cycle C in 0 L T Q n 1 F 0 , then N 0 L T Q n 1 ( C ) V ( 0 L T Q n 1 ) F 0 . By Proposition 7, | N 0 L T Q n 1 ( V ( C ) ) | 4 ( n 1 2 ) = 4 n 12 > 4 n 13 = | F 0 | , a contradiction to | F 0 | = 4 n 13 . Therefore, 0 L T Q n 1 F 0 has not a 4-cycle.

Case 5. 4 n 12 | F 0 | 4 n 9 .

Since 4 n 12 | F 0 | 4 n 9 and | F | 4 n 9 , | F 1 | ( 4 n 9 ) ( 4 n 12 ) = 3 . By Lemma 1, 1 L T Q n 1 F 1 is connected.

Suppose that 0 L T Q n 1 F 0 is connected. Since 2 n 1 ( 4 n 9 ) 1 , by Le- mma 3, L T Q n F is connected, a contradiction.

Suppose that 0 L T Q n 1 F 0 is not connected. Let the components in 0 L T Q n 1 F 0 be G 1 , G 2 , , G k for k 2 and | V ( G 1 ) | | V ( G 2 ) | | V ( G k ) | . If | V ( G r ) | 4 ( 1 r k 1 ) , by Lemma 3, | N ( V ( G r ) ) V ( 1 L T Q n 1 ) | 4 . If k 5 , by Lemma 3, | N ( V ( G 1 ) ) N ( V ( G 2 ) ) N ( V ( G k 1 ) ) V ( 1 L T Q n 1 ) | 4 . Combining this with | F 1 | ( 4 n 9 ) ( 4 n 12 ) = 3 , we have that L T Q n F satisfies one of the following conditions:

1) L T Q n F has four components, three of which are isolated vertices;

2) L T Q n F has three components, one of which is isolated vertices and one of which is a K 2 ;

3) L T Q n F has three components, two of which are isolated vertices;

4) L T Q n F has two components, one of which is a path of length two;

5) L T Q n F has two components, one of which is an isolated vertex;

6) L T Q n F has two components, one of which is a K 2 ;

7) L T Q n F is connected.

In this case, F is not a minimum 3-extra cut of L T Q n , 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 G = ( V , E ) is g-extra t-diagnosable under the PMC model if and only if there is an edge u v E with u V \ ( F 1 F 2 ) and v F 1 Δ F 2 for each distinct pair of g-extra faulty sub- sets F 1 and F 2 of V with | F 1 | t and | F 2 | t .

Lemma 11. Let n 4 . Then the 3-extra diagnosability of the locally twisted cube L T Q n under the PMC model is less than or equal to 4 n 6 , i.e., t ˜ 3 ( L T Q n ) 4 n 6 .

Proof. Let A be defined in Lemma 7, and let F 1 = N L T Q n ( A ) , F 2 = A N L T Q n ( A ) . By Lemma 7, | F 1 | = 4 n 9 , | F 2 | = | A | + | F 1 | = 4 n 5 , | V ( L T Q n [ A ] ) | 4 and | V ( L T Q n F 2 ) | 4 , F 1 is a 3-extra cut of L T Q n . Therefore, F 1 and F 2 are 3-extra faulty sets of L T Q n with | F 1 | = 4 n 9 and | F 2 | = 4 n 5 . Since A = F 1 Δ F 2 and N L T Q n ( A ) = F 1 F 2 , there is no edge of L T Q n between V ( L T Q n ) \ ( F 1 F 2 ) and F 1 Δ F 2 . By Theorem 10, we can deduce that L T Q n is not 3-extra ( 4 n 5 ) -diagnosable under PMC model. Hence, by the definition of 3-extra diagnosability, we conclude that the 3-extra diagnosability of L T Q n is less than 4 n 5 , i.e., t ˜ 3 ( L T Q n ) 4 n 6 .

Lemma 12. Let n 5 . Then the 3-extra diagnosability of the locally twisted cube L T Q n under the PMC model is more than or equal to 4 n 6 , i.e., t ˜ 3 ( L T Q n ) 4 n 6 .

Proof. By the definition of 3-extra diagnosability, it is sufficient to show that L T Q n is 3-extra ( 4 n 6 ) -diagnosable. By Theorem 10, to prove L T Q n is 3- extra ( 4 n 6 ) -diagnosable, it is equivalent to prove that there is an edge u v E ( L T Q n ) with u V ( L T Q n ) \ ( F 1 F 2 ) and v F 1 Δ F 2 for each distinct pair of 3-extra faulty subsets F 1 and F 2 of V ( L T Q n ) with | F 1 | 4 n 6 and | F 2 | 4 n 6 .

Suppose, by way of contradiction, that there are two distinct 3-extra faulty subsets F 1 and F 2 of L T Q n with | F 1 | 4 n 6 and | F 2 | 4 n 6 , but the vertex set pair ( F 1 , F 2 ) is not satisfied with the condition in Theorem 10, i.e., there are no edges between V ( L T Q n ) \ ( F 1 F 2 ) and F 1 Δ F 2 . Without loss of generality, assume that F 2 \ F 1 .

Assume V ( L T Q n ) = F 1 F 2 . Since n 5 , we have that 2 n = | V ( L T Q n ) | = | F 1 F 2 | = | F 1 | + | F 2 | | F 1 F 2 | | F 1 | + | F 2 | ( 4 n 6 ) + ( 4 n 6 ) = 8 n 12 , a contra- diction. Therefore, V ( L T Q n ) F 1 F 2 .

The following we discuss the case when F 2 \ F 1 and V ( L T Q n ) F 1 F 2 .

Since there are no edges between V ( L T Q n ) \ ( F 1 F 2 ) and F 1 Δ F 2 , and F 1 is a 3-extra faulty set, L T Q n F 1 has two parts L T Q n F 1 F 2 and L T Q n [ F 2 \ F 1 ] . Thus, every component G i of L T Q n F 1 F 2 satisfies | V ( G i ) | 4 and every component C i of L T Q n [ F 2 \ F 1 ] satisfies | V ( C i ) | 4 . Similarly, every component C i of L T Q n [ F 1 \ F 2 ] satisfies | V ( C i ) | 4 when F 1 \ F 2 . Therefore, F 1 F 2 is also a 3-extra faulty set. Since there are no edges between V ( L T Q n F 1 F 2 ) and F 1 Δ F 2 , F 1 F 2 is also a 3-extra cut. When F 1 \ F 2 = , F 1 F 2 = F 1 is also a 3-extra faulty set. Since there are no edges between V ( L T Q n F 1 F 2 ) and F 1 Δ F 2 , F 1 F 2 is a 3-extra cut. By Theorem 8, | F 1 F 2 | 4 n 9 . Therefore, | F 2 | = | F 2 \ F 1 | + | F 1 F 2 | 4 + 4 n 9 = 4 n 5 , which contradicts with that | F 2 | 4 n 6 . So L T Q n is 3-extra ( 4 n 6 ) -diagnosable. By the definition of t ˜ 3 ( L T Q n ) , t ˜ 3 ( L T Q n ) 4 n 6 . The proof is complete.

Combining Lemmas 11 and 12, we have the following theorem.

Theorem 11. Let n 5 . Then the 3-extra diagnosability of the locally twisted cubes L T Q n under the PMC model is 4 n 6 .

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 L T Q n under the MM* model, we first give an existing result.

Theorem 12 ( [3] [16] [26] ) A system G = ( V , E ) is g-extra t-diagnosable under the MM* model if and only if for each distinct pair of g-extra faulty sub- sets F 1 and F 2 of V with | F 1 | t and | F 2 | t satisfies one of the following conditions.

1) There are two vertices u , w V \ ( F 1 F 2 ) and there is a vertex v F 1 Δ F 2 such that u w E and v w E .

2) There are two vertices u , v F 1 \ F 2 and there is a vertex w V \ ( F 1 F 2 ) such that u w E and v w E .

3) There are two vertices u , v F 2 \ F 1 and there is a vertex w V \ ( F 1 F 2 ) such that u w E and v w E .

Lemma 13. Let n 4 . Then the 3-extra diagnosability of the locally twisted cube L T Q n under the MM* model is less than or equal to 4 n 6 , i.e., t ˜ 3 ( L T Q n ) 4 n 6 .

Proof. Let A be defined in Lemma 7, and let F 1 = N L T Q n ( A ) , F 2 = A N L T Q n ( A ) . By Lemma 7, | F 1 | = 4 n 9 , | F 2 | = | A | + | F 1 | = 4 n 5 , | V ( L T Q n [ A ] ) | 4 and | V ( L T Q n F 2 ) | 4 , F 1 is a 3-extra cut of L T Q n . Therefore, F 1 and F 2 are 3-extra faulty sets of L T Q n with | F 1 | = 4 n 9 and | F 2 | = 4 n 5 . Since A = F 1 Δ F 2 and N L T Q n ( A ) = F 1 F 2 , there is no edge of L T Q n between V ( L T Q n ) \ ( F 1 F 2 ) and F 1 Δ F 2 . By Theorem 12, we can deduce that L T Q n is not 3-extra ( 4 n 5 ) -diagnosable under MM* model. Hence, by the definition of 3-extra diagnosability, we conclude that the 3-extra diagnosability of L T Q n is less than 4 n 5 , i.e., t ˜ 3 ( L T Q n ) 4 n 6 .

A component of a graph G is odd or even according as it has an odd or even number of vertices. We denote by o ( G ) the number of odd components of G.

Lemma 14. ( [20] ) A graph G = ( V , E ) has a perfect matching if and only if o ( G S ) | S | for all S V .

Lemma 15. Let n 7 . Then the 3-extra diagnosability of the locally twisted cube L T Q n under the MM* model is more than or equal to 4 n 6 , i.e., t ˜ 3 ( L T Q n ) 4 n 6 .

Proof. By the definition of the 3-extra diagnosability, it is sufficient to show that L T Q n is 3-extra ( 4 n 6 ) -diagnosable.

By Theorem 12, suppose, by way of contradiction, that there are two distinct 3-extra faulty subsets F 1 and F 2 of L T Q n with | F 1 | 4 n 6 and | F 2 | 4 n 6 , but the vertex set pair ( F 1 , F 2 ) is not satisfied with any one condition in Theorem 12. Without loss of generality, assume that F 2 \ F 1 . Similarly to the discussion on V ( L T Q n ) = F 1 F 2 in Lemma 12, we can deduce V ( L T Q n ) F 1 F 2 . Therefore, we have the following discussion for V ( L T Q n ) F 1 F 2 .

Claim 1. L T Q n F 1 F 2 has no isolated vertex.

Suppose, by way of contradiction, that L T Q n F 1 F 2 has at least one isolated vertex w. Since F 1 is a 3-extra faulty set, there is at least one vertex u F 2 \ F 1 such that u are adjacent to w. Since the vertex set pair ( F 1 , F 2 ) is not satisfied with any one condition in Theorem 12, by the condition (3) of Theorem 12, there is at most one vertex u F 2 \ F 1 such that u is adjacent to w. Therefore, there is just a vertex u is adjacent to w.

Case 1. F 1 \ F 2 = .

If F 1 \ F 2 = , then F 1 F 2 . Since F 2 is a 3-extra faulty set, every com- ponent G i of L T Q n F 1 F 2 has | V ( G i ) | 4 . Thus, L T Q n F 1 F 2 has no isolated vertex.

Case 2. F 1 \ F 2 .

Similarly, since F 1 \ F 2 , by the condition (2) of Theorem 12 and the hypothesis, we can deduce that there is just a vertex v F 1 \ F 2 such that v is adjacent to w.

Let W V ( L T Q n ) \ ( F 1 F 2 ) be the set of isolated vertices in L T Q n [ V ( L T Q n ) \ ( F 1 F 2 ) ] , and H be the induced subgraph by the vertex set V ( L T Q n ) \ ( F 1 F 2 W ) . Then for any w W , there are ( n 2 ) neighbors in F 1 F 2 . By Lemmas 14 and 3, | W | o ( L T Q n ( F 1 F 2 ) ) | F 1 F 2 | = | F 1 | + | F 2 | | F 1 F 2 | ( 4 n 6 ) + ( 4 n 6 ) ( n 2 ) = 7 n 10 . Assume V ( H ) = . Then 2 n = | V ( L T Q n ) | = | F 1 F 2 | + | W | = | F 1 | + | F 2 | | F 1 F 2 | ( 4 n 6 ) + ( 4 n 6 ) ( n 2 ) + ( 7 n 10 ) = 14 n 20 , a contradiction to that n 7 . So V ( H ) .

The following we discuss the case when F 1 \ F 2 , F 2 \ F 1 and V ( H ) .

Since the vertex set pair ( F 1 , F 2 ) is not satisfied with the condition (1) of Theorem 12, and there are not isolated vertices in H , we induce that there is no edge between V ( H ) and F 1 Δ F 2 . Note that F 2 \ F 1 . If F 1 F 2 = , then this is a contradiction to that L T Q n is connected. Therefore, F 1 F 2 . Thus, F 1 F 2 is a vertex cut of L T Q n . Since F 1 is a 3-extra faulty set of L T Q n , we have that every component H i of H has | V ( H i ) | 4 and every component C i of L T Q n [ W ( F 2 \ F 1 ) ] has | V ( C i ) | 4 . Since F 2 also is a 3-extra faulty set of L T Q n , we have that every component C i of L T Q n [ W ( F 1 \ F 2 ) ] has | V ( C i ) | 4 . Note that L T Q n ( F 1 F 2 ) has two parts: H and L T Q n [ W ( F 1 Δ F 2 ) ] . Let b i V ( L T Q n [ W ( F 1 Δ F 2 ) ] ) . If b i W , then b i has two neighbors u V ( C i ) and v V ( C i ) . Then b i V ( C i C i ) and | V ( C i C i ) | 4 . Thus, F 1 F 2 is a 3-extra cut of L T Q n . By Theorem 8, | F 1 F 2 | 4 n 9 . Since | V ( C i ) | 4 , | F 2 \ F 1 | 3 . Since | F 1 F 2 | = | F 2 | | F 2 \ F 1 | ( 4 n 6 ) 3 = 4 n 9 , we have | F 1 F 2 | = 4 n 9 . Then | F 2 \ F 1 | = 3 and | F 2 | = 4 n 6 . Similarly, | F 1 \ F 2 | = 3 , | F 1 | = 4 n 6 . By Lemma 9, the locally twisted cube L T Q n is tightly ( 4 n 9 ) super 3-extra connected, i.e., L T Q n ( F 1 F 2 ) has two components, one of which is a subgraph of or- der 4. Noted that | W | 7 n 10 . 2 n = | V ( L T Q n ) | = | F 1 \ F 2 | + | F 2 \ F 1 | + | F 1 F 2 | + | V ( H ) | + | W | 3 + 3 + ( 4 n 9 ) + 4 + ( 7 n 10 ) = 11 n 9 , a contradiction to n 7 . Therefore, L T Q n F 1 F 2 has no isolated vertex when F 1 \ F 2 , F 2 \ F 1 and V ( H ) . The proof of Claim 1 is complete.

Let u V ( L T Q n ) \ ( F 1 F 2 ) . By Claim 1, u has at least one neighbor vertex in L T Q n F 1 F 2 . Since the vertex set pair ( F 1 , F 2 ) is not satisfied with any one condition in Theorem 12, by the condition (1) of Theorem 12, for any pair of adjacent vertices u , w V ( L T Q n ) \ ( F 1 F 2 ) , there is no vertex v F 1 Δ F 2 such that u w E ( L T Q n ) and u v E ( L T Q n ) . It follows that u has no neighbor vertex in F 1 Δ F 2 . By the arbitrariness of u, there is no edge between V ( L T Q n ) \ ( F 1 F 2 ) and F 1 Δ F 2 . Since F 2 \ F 1 and F 1 is a 3-extra faulty set, | F 2 \ F 1 | 4 and | V ( L T Q n F 2 F 1 ) | 4 . Since F 1 also is 3-extra faulty sets, | F 1 \ F 2 | 4 and | V ( L T Q n F 1 F 2 ) | 4 . Then F 1 F 2 is a 3- extra cut of L T Q n . By Theorem 8, we have | F 1 F 2 | 4 n 9 . Therefore, | F 2 | = | F 2 \ F 1 | + | F 1 F 2 | 4 + ( 4 n 9 ) = 4 n 5 , which contradicts | F 2 | 4 n 6 . Therefore, L T Q n is 3-extra ( 4 n 6 ) -diagnosable and t ˜ 3 ( L T Q n ) 4 n 6 . The proof is complete.

Combining Lemmas 13 and 15, we have the following theorem.

Theorem 13. Let n 7 . Then the 3-extra diagnosability of the locally twisted cube L T Q n under the MM* model is 4 n 6 .

Acknowledgements

This work is supported by the National Science Foundation of China (61370001).

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1] Preparata, F.P., Metze, G. and Chien, R.T. (1967) On the Connection Assignment Problem of Diagnosable Systems. IEEE Transactions on Computers, EC-16, 848-854.
https://doi.org/10.1109/PGEC.1967.264748
[2] Maeng, J. and Malek, M. (1981) A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor Systems. Proceeding of 11th International Symposium on Fault-Tolerant Computing, 173-175.
[3] Sengupta, A. and Dahbura, A.T. (1992) On Self-Diagnosable Multiprocessor Systems: Diagnosis by the Comparison Approach. IEEE Transactions on Computers, 41, 1386-1396.
https://doi.org/10.1109/12.177309
[4] Fàbrega, J. and Fiol, M.A. (1996) On the Extraconnectivity of Graphs. Discrete Mathematics, 155, 49-57.
[5] Gu, M.-M., Hao, R.-X. and Liu J.-B. (2017) On the Extraconnectivity of k-Ary n-Cube Networks. International Journal of Computer Mathematics, 94, 95-106.
https://doi.org/10.1080/00207160.2015.1091070
[6] Chang, N.-W., Tsai, C.-Y. and Hsieh, S.-Y. (2014) On 3-Extra Connectivity and 3-Extra Edge Connectivity of Folded Hypercubes. IEEE Transactions on Computers, 63, 1593-1599.
[7] Zhang, M.-M. and Zhou, J.-X. (2015) On g-Extra Connectivity of Folded Hypercubes. Theoretical Computer Science, 593, 146-153.
[8] Hsieh, S.-Y. and Chang, Y.-H. (2012) Extraconnectivity of k-Ary n-Cube Networks. Theoretical Computer Science, 443, 63-69.
[9] Gu, M.-M. and Hao, R.-X. (2014) 3-Extra Connectivity of 3-Ary n-Cube Networks. Information Processing Letters, 114, 486-491.
[10] Lin, R.Z. and Zhang, H.P. (2016) The Restricted Edge-Connectivity and Restricted Connectivity of Augmented k-Ary n-Cubes. International Journal of Computer Mathematics, 93, 1281-1298.
https://doi.org/10.1080/00207160.2015.1067690
[11] Lü, H. (2017) On Extra Connectivity and Extra Edge-Connectivity of Balanced Hypercubes. International Journal of Computer Mathematics, 94, 813-820.
https://doi.org/10.1080/00207160.2016.1148813
[12] Hong, W.-S. and Hsieh, S.-Y. (2013) Extra Edge Connectivity of Hypercube-Like Networks. International Journal of Parallel, Emergent and Distributed Systems, 28, 123-133.
https://doi.org/10.1080/17445760.2011.650696
[13] Xu, J.M., Wang, J.W. and Wang, W.W. (2010) On Super and Restricted Connectivity of Some Interconnection Networks. Ars Combinatoria, 94, 1-8.
[14] Peng, S.-L., Lin, C.-K., Tan, J.J.M. and Hsu, L.-H. (2012) The g-Good-Neighbor Conditional Diagnosability of Hypercube under PMC Model. Applied Mathematics and Computation, 218, 10406-10412.
https://doi.org/10.1016/j.amc.2012.03.092
[15] Wang, S. and Han, W. (2016) The g-Good-Neighbor Conditional Diagnosability of n-Dimensional Hypercubes under the MM* Model. Information Processing Letters, 116, 574-577.
https://doi.org/10.1016/j.ipl.2016.04.005
[16] Zhang, S. and Yang, W. (2016) The g-Extra Conditional Diagnosability and Sequential t/k-Diagnosability of Hypercubes. International Journal of Computer Mathematics, 93, 482-497.
https://doi.org/10.1080/00207160.2015.1020796
[17] Ren, Y. and Wang, S. The Tightly Super 2-Extra Connectivity and 2-Extra Diagnosability of Locally Twisted Cubes. Journal of Interconnection Networks (To Appear).
[18] Wang, S., Wang, Z. and Wang, M. (2016) The 2-Extra Connectivity and 2-Extra Diagnosability of Bubble-Sort Star Graph Networks. The Computer Journal, 59, 1839-1856.
https://doi.org/10.1093/comjnl/bxw037
[19] Wang, S. and Yang, Y. (2017) The 2-Good-Neighbor (2-Extra) Diagnosability of Alternating Group Graph Networks under the PMC Model and MM* Model. Applied Mathematics and Computation, 305, 241-250.
https://doi.org/10.1016/j.amc.2017.02.006
[20] Bondy, J.A. and Murty, U.S.R. (2007) Graph Theory. Springer, New York.
[21] Ren, Y. and Wang, S. (2016) Some Properties of the g-Good-Neighbor (g-Extra) Diagnosability of a Multiprocessor System. American Journal of Computational Mathematics, 6, 259-266.
https://doi.org/10.4236/ajcm.2016.63027
[22] Dahbura, A.T. and Masson, G.M. (1984) An O(n2.5) Fault Identification Algorithm for Diagnosable Systems. IEEE Transactions on Computers, 33, 486-492.
https://doi.org/10.1109/TC.1984.1676472
[23] Fan, J. (2002) Diagnosability of Crossed Cubes under the Comparison Diagnosis Model. IEEE Transactions on Parallel and Distributed Systems, 13, 1099-1104.
https://doi.org/10.1109/TPDS.2002.1041887
[24] Fan, J., Zhang, S., Jia, X. and Zhang, G. (2009) The Restricted Connectivity of Locally Twisted Cubes. 10th International Symposium on Pervasive Systems, Algorithms, and Networks (ISPAN), Kaohsiung, 14-16 December 2009, 574-578.
https://doi.org/10.1109/I-SPAN.2009.48
[25] Lai, P.-L., Tan, J.J.M., Chang, C.-P. and Hsu, L.-H. (2005) Conditional Diagnosability Measures for Large Multiprocessor Systems. IEEE Transactions on Computers, 54, 165-175.
https://doi.org/10.1109/TC.2005.19
[26] Yuan, J., Liu, A., Ma, X., Liu, X., Qin, X. and Zhang, J. (2015) The g-Good-Neighbor Conditional Diagnosability of k-Ary n-Cubes under the PMC model and MM* Model. IEEE Transactions on Parallel and Distributed Systems, 26, 1165-1177.
https://doi.org/10.1109/TPDS.2014.2318305
[27] Yang, X., Evans, D.J. and Megson, G.M. (2005) The Locally Twisted Cubes. International Journal of Computer Mathematics, 82, 401-413.
https://doi.org/10.1080/0020716042000301752
[28] Ren, Y. and Wang, S. The 1-Good-Neighbor Connectivity and Diagnosability of Locally Twisted Cubes. Chinese Quarterly Journal of Mathematics (To Appear).
[29] Feng, R., Bian, G. and Wang, X. (2011) Conditional Diagnosability of the Locally Twisted Cubes under the PMC Model. Communications and Network, 3, 220-224.
https://doi.org/10.4236/cn.2011.34025
[30] Hsieh, S.-Y., Huang, H.-W. and Lee, C.-W. (2016) {2,3}-Restricted Connectivity of Locally Twisted Cubes. Theoretical Computer Science, 615, 78-90.
https://doi.org/10.1016/j.tcs.2015.11.050
[31] Zhu, Q., Wang, X.-K. and Cheng, G. (2013) Reliability Evaluation of BC Networks. IEEE Transactions on Computers, 62, 2337-2340.
https://doi.org/10.1109/TC.2012.106

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.