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 $\left(g+1\right)$ vertices. The locally twisted cube $LT{Q}_n$ is applied widely. In this paper, we show that $LT{Q}_n$ is tightly $\left(4n-9\right)$ super 3-extra connected for $n\ge 6$ and the 3-extra diagnosability of $LT{Q}_n$ under the PMC model and MM^* model is $4n-6$ for $n\ge 5$ and $n\ge 7$ , respectively.

Keywords:

Interconnection Network, Combinatorics, Diagnosability

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 ${\tilde{\kappa }}^{\left(g\right)}\left(G\right)$ of an interconnection network G was introduced by Fàbrega and Fiol [4] . The g-extra connectivity ${\tilde{\kappa }}^{\left(g\right)}\left(G\right)$ 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 $\left(g+1\right)$ 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 $LT{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 $LT{Q}_n$ is tightly $\left(4n-9\right)$ super 3-extra con- nected for $n\ge 6$ and the 3-extra diagnosability of $LT{Q}_n$ under the PMC model and MM^* model is $4n-6$ for $n\ge 5$ and $n\ge 7$ , respectively.

2. Preliminaries

2.1. Notations

A multiprocessor system is modeled as an undirected simple graph $G=\left(V,E\right)$ , whose vertices (nodes) represent processors and edges (links) represent com- munication links. Suppose that $V^{\prime }$ is a nonempty vertex subset of V. The in- duced subgraph by $V^{\prime }$ in G, denoted by $G\left[V^{\prime }\right]$ , is a graph, whose vertex set is $V^{\prime }$ and whose edge set consists of all the edges of G with both endpoints in $V^{\prime }$ . The degree $d_G\left(v\right)$ of a vertex v in G is the number of edges incident with v. We denote by $\delta \left(G\right)$ the minimum degree of vertices of G. For any vertex v, we define the neighborhood $N_G\left(v\right)$ 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\in N_G\mathrm{<mo\; stretchy="false">\; (\; </mo>}v\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ . Let $S\subseteq V\left(G\right)$ . We denote by $N_G\left(S\right)$ the set ${\displaystyle {\cup }_{v\in S}{N}_G\left(v\right)}\backslash 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\left(v\right)=k$ for any vertex $v\in 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 $\left(X\mathrm{,}Y\right)$ is called a bipartition of the graph. A complete bipartite graph is a simple bipartite graph with bipartition $\left(X\mathrm{,}Y\right)$ in which each vertex of X is joined to each vertex of Y; if $\left|X\right|=m$ and $\left|Y\right|=n$ , such a graph is denoted by $K_{m\mathrm{,}n}$ . The connectivity $\kappa \left(G\right)$ 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\Delta F_2=\left(F_1\backslash F_2\right)\cup \left(F_2\backslash F_1\right)$ . For graph-theoretical terminology and notation not defined here we follow [20] .

Let $G=\left(V,E\right)$ be a connected graph. A faulty set $F\subseteq V$ is called a g- good-neighbor faulty set if $\left|N\left(v\right)\cap \left(V\backslash F\right)\right|\ge g$ for every vertex v in $V\backslash 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 ${\kappa }^{\left(g\right)}\left(G\right)$ . A faulty set $F\subseteq V$ is called a g-extra faulty set if every component of $G-F$ has at least $\left(g+1\right)$ 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 ${\tilde{\kappa }}^{\left(g\right)}\left(G\right)$ .

Proposition 1. ( [21] ) Let G be a g-extra and g-good-neighbor connected graph. Then ${\tilde{\kappa }}^{\left(g\right)}\left(G\right)\le {\kappa }^{\left(g\right)}\left(G\right)$ .

Proposition 2. ( [21] ) Let G be a 1-good-neighbor connected graph. Then ${\kappa }^{\left(1\right)}\left(G\right)={\tilde{\kappa }}^{\left(1\right)}\left(G\right)$ .

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=\left(V\left(G\right),E\left(G\right)\right)$ , two adjacent nodes in G are capable to perform tests on each other. For two adjacent nodes u and v in $V\left(G\right)$ , the test performed by u on v is represented by the ordered pair $\left(u\mathrm{,}v\right)$ . The outcome of a test $\left(u\mathrm{,}v\right)$ 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 $\sigma$ , a subset of vertices $F\subseteq V\left(G\right)$ is said to be consistent with $\sigma$ if syndrome $\sigma$ can be produced from the situation that, for any $\left(u\mathrm{,}v\right)\in L$ such that $u\in V\backslash F$ , $\sigma \left(u,v\right)=1$ if and only if $v\in F$ . Let $\sigma \left(F\right)$ 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\left(G\right)$ are said to be indistinguishable if $\sigma \left(F_1\right)\cap \sigma \left(F_2\right)\ne \varnothing$ , otherwise, $F_1$ and $F_2$ are said to be distinguishable.

Similar to the PMC model, we can define a subset of vertices $F\subseteq V\left(G\right)$ is consistent with a given syndrome ${\sigma }^{\mathrm{<mo>\; *\; </mo>}}$ and two distinct sets $F_1$ and $F_2$ in $V\left(G\right)$ are indistinguishable (resp. distinguishable) under the MM^* model.

In a system $G=\left(V,E\right)$ , a faulty set $F\subseteq 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\mathrm{,}{F}_2\subseteq V\left(G\right)$ such that $\left|F_i\right|\le t$ , $F_1$ and $F_2$ are distinguishable. The g-extra diagnosability of G, denoted by ${\tilde{t}}_g\left(G\right)$ , is the maximum value of t such that G is g-extra t- diagnosable.

Proposition 4. [18] For any given system G, ${\tilde{t}}_g\left(G\right)\le {\tilde{t}}_{g^{\prime }}\left(G\right)$ if $g\le g^{\prime }$ .

For an integer $n\ge 1$ , a binary string of length n is denoted by $u_1{u}_2\cdots u_n$ , where $u_i\in \left\{\mathrm{0,1}\right\}$ for any integer $i\in \left\{\mathrm{1,2,}\cdots \mathrm{,}n\right\}$ . The n-dimensional locally twisted cube, denoted by $LT{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\ge 2$ , an n-dimensional locally twisted cube, denoted by $LT{Q}_n$ , is defined recursively as follows:

1) $LT{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\ge 3$ , $LT{Q}_n$ is built from two disjoint copies of $LT{Q}_{n-1}$ according to the following steps. Let $0LT{Q}_{n-1}$ denote the graph obtained from one copy of $LT{Q}_{n-1}$ by prefixing the label of each node with 0. Let $1LT{Q}_{n-1}$ denote the graph obtained from the other copy of $LT{Q}_{n-1}$ by prefixing the label of each node with 1. Connect each node $0u_2{u}_3\cdots u_n$ of $0LT{Q}_{n-1}$ to the node $1\left(u_2+u_n\right)u_3\cdots u_n$ of $1LT{Q}_{n-1}$ with an edge, where “+” represents the modulo 2 addition.

The edges whose end vertices in different $iLT{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\ge 2$ , the n-dimensional locally twisted cube, denoted by $LT{Q}_n$ , is a graph with ${\left\{\mathrm{0,1}\right\}}^n$ as the node set. Two nodes $u_1{u}_2\cdots u_n$ and $v_1{v}_2\cdots v_n$ of $LT{Q}_n$ are adjacent if and only if either one of the following conditions are satisfied.

1) $u_i=\overline{v_i}$ and $u_{i+1}=\left(v_{i+1}+v_n\right)\left(mod2\right)$ for some $1\le i\le n-2$ , $n\ge 3$ and $u_j=v_j$ for all the remaining bits;

2) $u_i=\overline{v_i}$ for $i\in \left\{n-\mathrm{1,}n\right\}$ , $n\ge 2$ and $u_j=v_j$ for all the remaining bits.

Proposition 7. ( [28] ) Let $LT{Q}_n$ be the locally twisted cube. If two vertices $u\mathrm{,}v$ are adjacent, there is no common neighbor vertex of these two vertices, i.e., $\left|N\left(u\right)\cap N\left(v\right)\right|=0$ . If two vertices $u\mathrm{,}v$ are not adjacent, there are at most two common neighbor vertices of these two vertices, i.e., $\left|N\left(u\right)\cap N\left(v\right)\right|\le 2$ .

3. The Connectivity of Locally Twisted Cubes

Lemma 1. ( [27] ) Let $LT{Q}_n$ be the locally twisted cube. Then $\kappa \left(LT{Q}_n\right)=n$ .

Lemma 2. ( [29] ) Let $LT{Q}_n$ be the locally twisted cube, and let $S\subseteq V\left(LT{Q}_n\right)$ and $n\ge 3$ . If $LT{Q}_n-S$ is disconnected and $n\le \left|S\right|\le 2n-3$ , then $LT{Q}_n-S$ has exactly two components, one is trivial and the other is nontrivial.

Lemma 3. ( [17] ) Let $LT{Q}_n$ be the locally twisted cube. Then all cross-edges of $LT{Q}_n$ is a perfect matching.

Lemma 4. ( [30] ) Let $LT{Q}_n$ be the locally twisted cube. Then ${\kappa }^{\left(2\right)}\left(LT{Q}_n\right)=4n-8$ .

Lemma 5. Let $LT{Q}_n$ be the locally twisted cube. If $P=uvwx$ is a 3-path in $LT{Q}_n$ and $ux\notin E\left(LT{Q}_n\right)$ for $n\ge 3$ , $\left|N\left(V\left(P\right)\right)\right|\ge 4n-9$ .

Proof. We decompose $LT{Q}_n$ into $0LT{Q}_{n-1}$ and $1LT{Q}_{n-1}$ . Then $0LT{Q}_{n-1}$ and $1LT{Q}_{n-1}$ are isomorphic to $LT{Q}_{n-1}$ . Without loss of generality, we have the following cases.

Case 1. $u\mathrm{,}x\in V\left(0LT{Q}_{n-1}\right)$ and $v\mathrm{,}w\in V\left(1LT{Q}_{n-1}\right)$ .

Since $u\in V\left(0LT{Q}_{n-1}\right)$ , $v\in V\left(1LT{Q}_{n-1}\right)$ and $u\mathrm{,}v$ are adjacent, by Propo- sition 7, $u\mathrm{,}v$ have no the common neighbor vertex. Similarly, $x\mathrm{,}w$ have no the common neighbor vertex and $v\mathrm{,}w$ have no the common neighbor vertex. Since $u\in V\left(0LT{Q}_{n-1}\right)$ , $w\in V\left(1LT{Q}_{n-1}\right)$ , $u\mathrm{,}w$ are not adjacent, v is a com- mon neighbor vertex of $u\mathrm{,}w$ , $x\in V\left(0LT{Q}_{n-1}\right)$ and x is a neighbor vertex of w, by Lemma 3, $\left|\left(N\left(u\right)\cap N\left(w\right)\right)\backslash \left\{v\right\}\right|=0$ . Similarly, $\left|\left(N\left(x\right)\cap N\left(v\right)\right)\backslash \left\{w\right\}\right|=0$ . Since u and x are not adjacent, by proposition 7, $\left|N\left(u\right)\cap N\left(x\right)\right|\le 2$ . Therefore, $\left|N\left(V\left(P\right)\right)\right|\ge 2\left(n-1\right)+2\left(n-2\right)-2=4n-8$ .

Case 2. $u\in V\left(0LT{Q}_{n-1}\right)$ and $v\mathrm{,}w\mathrm{,}x\in V\left(1LT{Q}_{n-1}\right)$ .

Since $u\mathrm{,}v$ are adjacent, by Proposition 7, $\left|N\left(u\right)\cap N\left(v\right)\right|=0$ . Similarly, $\left|N\left(v\right)\cap N\left(w\right)\right|=0$ , $\left|N\left(x\right)\cap N\left(w\right)\right|=0$ . And since $u\in V\left(0LT{Q}_{n-1}\right)$ , $w\in V\left(1LT{Q}_{n-1}\right)$ , $u\mathrm{,}w$ are not adjacent and v is the common neighbor vertex of u and w, by Lemma 3, $\left|\left(N\left(u\right)\cap N\left(w\right)\right)\backslash \left\{v\right\}\right|\le 1$ . Since $u\mathrm{,}x$ are not adjacent, $u\in V\left(0LT{Q}_{n-1}\right)$ , $x\in V\left(1LT{Q}_{n-1}\right)$ , by Lemma 3, $\left|N\left(u\right)\cap N\left(x\right)\right|\le 1$ . Since w is the common neighbor vertex of v and x and $v\mathrm{,}x$ are not adjacent, by pro- position 7, $\left|\left(N\left(v\right)\cap N\left(x\right)\right)\backslash \left\{w\right\}\right|\le 1$ . Therefore, $\left|N\left(P\right)\right|\ge 2\left(n-1\right)+2\left(n-2\right)-3=4n-9$ .

Case 3. $u\mathrm{,}v\in V\left(0LT{Q}_{n-1}\right)$ and $w\mathrm{,}x\in V\left(1LT{Q}_{n-1}\right)$ .

Since $u\mathrm{,}v$ are adjacent, by Proposition 7, $\left|N\left(u\right)\cap N\left(v\right)\right|=0$ . Similarly, $\left|N\left(u\right)\cap N\left(w\right)\right|=0$ , $\left|N\left(w\right)\cap N\left(x\right)\right|=0$ . Since $u\in V\left(0LT{Q}_{n-1}\right)$ , $x\in V\left(1LT{Q}_{n-1}\right)$ and u, x are not adjacent, by proposition 7, $\mathrm{<mo>\; |\; </mo>}N\mathrm{<mo\; stretchy="false">\; (\; </mo>}u\mathrm{<mo\; stretchy="false">\; )\; </mo>}\cap N\mathrm{<mo\; stretchy="false">\; (\; </mo>}x\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo>\; |\; </mo>}\le 2$ . If $\left|\left(N\left(u\right)\cap N\left(w\right)\right)\backslash \left\{v\right\}\right|=1$ , then, by Lemma 3, $\left|N\left(u\right)\cap N\left(x\right)\right|\le 1$ . If $\left|\left(N\left(u\right)\cap N\left(w\right)\right)\backslash \left\{v\right\}\right|=0$ , then, by Lemma 3, $\left|N\left(u\right)\cap N\left(x\right)\right|\le 2$ . Therefore, $\left|N\left(V\left(P\right)\right)\right|\ge 2\left(n-1\right)+2\left(n-2\right)-2=4n-8$ .

Case 4. $u\mathrm{,}v\mathrm{,}w\mathrm{,}x\in V\left(1LT{Q}_{n-1}\right)$ .

This case is clear.

In conclusion, $\left|N\left(V\left(P\right)\right)\right|\ge 4n-9$ .

Lemma 6. Let $LT{Q}_n$ be the locally twisted cube. If $LT{Q}_n\left[\left\{u\mathrm{,}v\mathrm{,}w\mathrm{,}x\right\}\right]$ is isomorphic to $K_{\mathrm{1,3}}$ for $n\ge 3$ and $d\left(u\right)=3$ , then $\left|N\left(V\left(LT{Q}_n\left[\left\{u\mathrm{,}v\mathrm{,}w\mathrm{,}x\right\}\right]\right)\right)\right|\ge 4n-9$ .

Proof. Since $d\left(u\right)=3$ and $LT{Q}_n\left[\left\{u\mathrm{,}v\mathrm{,}w\mathrm{,}x\right\}\right]$ is isomorphic to $K_{\mathrm{1,3}}$ , we have $d\left(v\right)=1$ , $d\left(w\right)=1$ and $d\left(x\right)=1$ . Since $v\mathrm{,}w$ are not adjacent and u is a common neighbor vertex of v, w, by Proposition 7, $\left|\left(N\left(v\right)\cap N\left(w\right)\right)\backslash \left\{u\right\}\right|\le 1$ . Similarly, $\left|\left(N\left(v\right)\cap N\left(x\right)\right)\backslash \left\{u\right\}\right|\le 1$ , $\left|\left(N\left(w\right)\cap N\left(x\right)\right)\backslash \left\{u\right\}\right|\le 1$ . Therefore, $\left|N\left(V\left(LT{Q}_n\left[\left\{u,v,w,x\right\}\right]\right)\right)\right|\ge 3\left(n-1\right)+\left(n-3\right)-3=4n-9$ .

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

Corollary 1. Let $LT{Q}_n$ be the locally twisted cube and let H be a connected subgraph of $LT{Q}_n$ . If $\left|V\left(H\right)\right|\ge 4$ , then $\left|N\left(V\left(H\right)\right)\right|\ge 4n-9$ .

Lemma 7. Let $A=\left\{0\cdots \mathrm{0001,0}\cdots \mathrm{0111,0}\cdots \mathrm{0101,0}\cdots 0100\right\}$ and let $LT{Q}_n$ be the locally twisted cube with $n\ge 4$ . If $F_1=N_{LT{Q}_n}\left(A\right)$ , $F_2=F_1\cup A$ , where $n\ge 4$ , then $\left|F_1\right|=4n-9$ , $\left|F_2\right|=4n-5$ , $F_1$ is a 3-extra cut of $LT{Q}_n$ , $LT{Q}_n-F_1$ has two components $LT{Q}_n-F_2$ and $LT{Q}_n\left[A\right]$ , $\left|V\left(LT{Q}_n-F_2\right)\right|\ge 4$ , and $\left|A\right|\ge 4$ .

Proof. According to the definition, $LT{Q}_n\left[A\right]$ is a 3-path and $\left|A\right|=4$ . By Lemma 5, $\left|F_1\right|\ge 4n-9$ . From Figure 2 and the definition of $LT{Q}_n$ , we have that $\left|F_1\right|=2\left(n-3\right)+2\left(n-2\right)-3+4=4n-9$ . Therefore, $\left|F_2\right|=\left|F_1\right|+\left|A\right|=\left(4n-9\right)+4=4n-5$ . Let $F_2^i=V\left(iLT{Q}_{n-1}\right)\cap F_2$ , $i\in \left\{\mathrm{0,1}\right\}$ .

To prove $LT{Q}_n-F_2$ has two components and $\left|V\left(LT{Q}_n-F_2\right)\right|\ge 4$ , we have the following discussion.

Claim 1. $LT{Q}_n-F_2$ is connected for $n\ge 4$ .

The proof is by induction on n. For $n=4$ , $A=\left\{0001,0111,0101,0100\right\}$ , $F_1=\left\{0000,0011,0110,1001,1011,1101,1100\right\}$ . It is easy to see that $LT{Q}_4-F_2$ is connected (See Figure 2). When $n=5$ , $A=\left\{00001,00111,00101,00100\right\}$ ,

$F_2^1=\left\{11001,11110,11111,10100\right\}$ (See Figure 3). It is clear that $1LT{Q}_{n-1}-F_2^1$ is connected (See Figure 3). We discompose $LT{Q}_n$ into $0LT{Q}_{n-1}$ and $1LT{Q}_{n-1}$ . Assume that $n\ge 6$ , the result holds for $LT{Q}_{n-1}$ . Then $0LT{Q}_{n-1}-F_2^0$ is con- nected. Note that $A\subseteq V\left(0LT{Q}_{n-1}\right)$ and $\left|N\left(A\right)\cap V\left(1LT{Q}_{n-1}\right)\right|=4$ . By Lemma 1, $1LT{Q}_{n-1}-F_2^1$ is connected. By inductive hypothesis, $0LT{Q}_{n-1}-F_2^0$ is con- nected. Since $2^{n-1}\mathrm{<mo>\; >\; </mo>\; 4}n-5$ , by Lemma 3, $LT{Q}_n-F_2$ is connected. The proof of Claim 1 is complete.

By Claim 1, $LT{Q}_n-F_1$ has two components $LT{Q}_n-F_2$ and $LT{Q}_n\left[A\right]$ for $n\ge 4$ . Then $\left|V\left(LT{Q}_n-F_2\right)\right|=2^n-\left(4n-5\right)\ge 4$ for $n\ge 4$ . And since $\left|A\right|=4$ , $F_1$ is a 3-extra cut of $LT{Q}_n$ .

Lemma 8. ( [17] ) Let $LT{Q}_n\left(n\ge 4\right)$ be the locally twisted cube. If $\left|F\right|\le 3n-6$ , then $LT{Q}_n-F$ satisfies one of the following conditions:

1) $LT{Q}_n-F$ has three components, two of which are isolated vertices;

2) $LT{Q}_n-F$ has two components, one of which is an isolated vertex;

3) $LT{Q}_n-F$ has two components, one of which is a $K_2$ ;

4) $LT{Q}_n-F$ is connected.

Theorem 8. ( [31] ) Let $LT{Q}_n$ be the locally twisted cube. Then ${\tilde{\kappa }}^{\left(3\right)}\left(LT{Q}_n\right)=4n-9$ for $n\ge 4$ .

Lemma 9. Let $LT{Q}_n$ be the locally twisted cube. If $\left|F\right|=10$ for $n=5$ , then $LT{Q}_5-F$ satisfies one of the following conditions:

1) $LT{Q}_5-F$ has four components, three of which are isolated vertices;

2) $LT{Q}_5-F$ has three components, one of which is isolated vertices and one of which is a $K_2$ ;

3) $LT{Q}_5-F$ has three components, two of which are isolated vertices;

4) $LT{Q}_5-F$ has two components, one of which is a path of length two;

5) $LT{Q}_5-F$ has two components, one of which is an isolated vertex;

6) $LT{Q}_5-F$ has two components, one of which is a $K_2$ ;

7) $LT{Q}_5-F$ is connected.

Proof. We decompose $LT{Q}_5$ into $0LT{Q}_4$ and $1LT{Q}_4$ . Then $0LT{Q}_4$ and $1LT{Q}_4$ are isomorphic to $LT{Q}_4$ . Suppose that $F_i=F\cap V\left(iLT{Q}_4\right)$ , $i\in \left\{\mathrm{0,1}\right\}$ . Without loss of generality, let $\left|F_0\right|\ge \left|F_1\right|$ . And since $\left|F\right|=10$ , $5\le \left|F_0\right|\le 10$ , $0\le \left|F_1\right|\le 5$ . Let $C_i$ be the maximum component of $iLT{Q}_4-F_i$ , $i\in \left\{\mathrm{0,1}\right\}$ . We consider the following cases.

Case 1. $\left|F_0\right|=5$ .

Since $\left|F_0\right|=5$ and $\left|F\right|=10$ , $\left|F_1\right|=10-5=5$ . By Lemmas 1 and 2, both $0LT{Q}_4-F_0$ and $1LT{Q}_4-F_1$ are connected or has two components, one of which is an isolated vertex. Since $2^{5-1}-6-2\ge 1$ , by Lemma 3, $LT{Q}_n\left[V\left(C_0\right)\cup V\left(C_1\right)\right]$ is connected. Thus, $LT{Q}_5-F$ satisfies one of con- ditions:

1) $LT{Q}_5-F$ has three components, two of which are isolated vertices;

2) $LT{Q}_5-F$ has two components, one of which is an isolated vertex;

3) $LT{Q}_5-F$ has two components, one of which is a $K_2$ ;

4) $LT{Q}_5-F$ is connected.

Case 2. $\left|F_0\right|=6$ .

Since $\left|F_0\right|=6$ and $\left|F\right|=10$ , $\left|F_1\right|=10-6=4$ . By Lemmas 1 and 2, $1LT{Q}_4-F_1$ is connected or has two components, one of which is an isolated vertex. Since $\left|F_0\right|=6$ , by Lemma 8, $0LT{Q}_4-F_0$ satisfies one of the following conditions:

1) $0LT{Q}_4-F_0$ has three components, two of which are isolated vertices;

2) $0LT{Q}_4-F_0$ has two components, one of which is an isolated vertex;

3) $0LT{Q}_4-F_0$ has two components, one of which is a $K_2$ ;

4) $0LT{Q}_4-F_0$ is connected.

Then $LT{Q}_5-F$ satisfies one of the conditions (1)-(7).

Case 3. $\left|F_0\right|\ge 7$ .

Since $\left|F_0\right|\ge 7$ and $\left|F\right|=10$ , $\left|F_1\right|\le 10-7=3$ . By Lemma 1, $1LT{Q}_4-F_1$ is connected.

Suppose that $0LT{Q}_4-F_0$ is connected. Since $2^{5-1}-10\ge 1$ , by Lemma 3, $LT{Q}_n-F$ is connected.

Suppose that $0LT{Q}_4-F_0$ is not connected. Let the components in $0LT{Q}_4-F_0$ be $G_1,G_2,\cdots ,G_k$ for $k\ge 2$ and $\left|V\left(G_1\right)\right|\le \left|V\left(G_2\right)\right|\le \cdots \le \left|V\left(G_k\right)\right|$ . If $\left|V\left(G_r\right)\right|\ge 4\left(1\le r\le k-1\right)$ , by Lemma 3, $\left|N\left(V\left(G_r\right)\right)\cap V\left(1LT{Q}_4\right)\right|\ge 4$ . Combining this with $\left|F_1\right|\le 3$ , we have that $LT{Q}_5\left[V\left(G_r\right)\cup V\left(1LT{Q}_4-F_1\right)\right]$ is connected. Therefore, $G_r$ is not a component of $LT{Q}_5-F$ for $\left|V\left(G_r\right)\right|\ge 4$ . Therefore, $LT{Q}_5-F$ is connected. The following we discuss $G_r$ is a com- ponent of $LT{Q}_5-F$ with $\left|V\left(G_r\right)\right|\le 3\left(1\le r\le k-1\right)$ .

If $k=5$ , by Lemma 3, $\left|N\left(V\left(G_1\right)\right)\cup N\left(V\left(G_2\right)\right)\cup \cdots \cup N\left(V\left(G_{k-1}\right)\right)\cap V\left(1LT{Q}_4\right)\right|\ge 4$ . Combining this with $\left|F_1\right|\le 3$ , there is one $G_r\left(1\le r\le k-1\right)$ such that $LT{Q}_5\left[V\left(G_r\right)\cup V\left(1LT{Q}_4-F_1\right)\right]$ is connected. Thus, $k\le 4$ . Since $\left|F_1\right|=3$ , $k\le 4$ , and $\left|V\left(G_r\right)\right|\le 3\left(1\le r\le k-1\right)$ , $LT{Q}_5-F$ satisfies one of the conditions (1)-(7).

Lemma 10. Let $LT{Q}_n$ be the locally twisted cube. If $3n-5\le \left|F\right|\le 4n-10$ for $n\ge 5$ , then $LT{Q}_n-F$ satisfies one of the following conditions:

1) $LT{Q}_n-F$ has four components, three of which are isolated vertices;

2) $LT{Q}_n-F$ has three components, one of which is isolated vertices and one of which is a $K_2$ ;

3) $LT{Q}_n-F$ has three components, two of which are isolated vertices;

4) $LT{Q}_n-F$ has two components, one of which is a path of length two;

5) $LT{Q}_n-F$ has two components, one of which is an isolated vertex;

6) $LT{Q}_n-F$ has two components, one of which is a $K_2$ ;

7) $LT{Q}_n-F$ is connected.

Proof. By Lemma 9, the result holds for $n=5$ . We proceed by induction on n. Assume $n\ge 6$ and the result holds for $LT{Q}_{n-1}$ , i.e., if $3n-5\le \left|F\right|\le 4\left(n-1\right)-10=4n-14$ , then $LT{Q}_{n-1}-F$ satisfies one of the con- ditions (1)-(7) in Lemma 10. The following we prove $LT{Q}_n-F$ satisfies one of the conditions (1)-(7).

We decompose $LT{Q}_n$ into $0LT{Q}_{n-1}$ and $1LT{Q}_{n-1}$ . Then $0LT{Q}_{n-1}$ and $1LT{Q}_{n-1}$ are isomorphic to $LT{Q}_{n-1}$ . Suppose that $F_i=F\cap V\left(iLT{Q}_{n-1}\right)$ , $i\in \left\{\mathrm{0,1}\right\}$ . Without loss of generality, let $\left|F_0\right|\ge \left|F_1\right|$ . And since

$3n-5\le \left|F\right|\le 4n-10$ , $n\le \lceil \frac{3n-5}{2}\rceil \le \left|F_0\right|\le 4n-10$ , $0\le \left|F_1\right|\le \lfloor \frac{4n-10}{2}\rfloor \le 2n-5$ .

Let $C_i$ be the maximum component of $iLT{Q}_{n-1}-F_i$ , $i\in \left\{\mathrm{0,1}\right\}$ . We consider the following cases.

Case 1. $n\le \left|F_0\right|\le 3\left(n-1\right)-6=3n-9$ .

Since $\left|F_0\right|\ge \left|F_1\right|$ and $\left|F\right|\le 4n-10$ ,

$\left(4n-10\right)-\left(3n-9\right)=n-1\le \left|F_1\right|\le \lfloor \frac{4n-10}{2}\rfloor =2n-5$ . By Lemmas 1 and 2,

$1LT{Q}_{n-1}-F_1$ is connected or has two components, one of which is an isolated vertex. Since $n\le \left|F_0\right|\le 3\left(n-1\right)-6=3n-9$ , by lemma 8, $0LT{Q}_{n-1}-F_0$ satisfies one of the following conditions: 1) $0LT{Q}_{n-1}-F_0$ has three components, two of which are isolated vertices; 2) $0LT{Q}_{n-1}-F_0$ has two components, one of which is an isolated vertex; 3) $0LT{Q}_{n-1}-F_0$ has two components, one of which is a $K_2$ ; 4) $0LT{Q}_{n-1}-F_0$ is connected. Since $2^{n-1}-\left(4n-10\right)-3\ge 1$ , by Lemma 3, $LT{Q}_n\left[V\left(C_0\right)\cup V\left(C_1\right)\right]$ is connected. Thus, $LT{Q}_n-F$ satisfies one of con- ditions (1)-(7) in Lemma 10.

Case 2. $3n-8\le \left|F_0\right|\le 4n-14$ .

Since $\left|F_0\right|\ge \left|F_1\right|$ and $\left|F\right|\le 4n-10$ , $\left|F_1\right|\le \left(4n-10\right)-\left(3n-8\right)=n-2$ . By Le- mma 1, $1LT{Q}_{n-1}-F_1$ is connected. Since $3n-8\le \left|F_0\right|\le 4n-14$ , according to inductive hypothesis, $0LT{Q}_{n-1}-F_0$ satisfies one of the following conditions:

1) $0LT{Q}_{n-1}-F_0$ has four components, three of which are isolated vertices;

2) $0LT{Q}_{n-1}-F_0$ has three components, one of which is isolated vertices and one of which is a $K_2$ ;

3) $0LT{Q}_{n-1}-F_0$ has three components, two of which are isolated vertices;

4) $0LT{Q}_{n-1}-F_0$ has two components, one of which is a path of length two;

5) $0LT{Q}_{n-1}-F_0$ has two components, one of which is an isolated vertex;

6) $0LT{Q}_{n-1}-F_0$ has two components, one of which is a $K_2$ ;

7) $0LT{Q}_{n-1}-F_0$ is connected.

Thus, $LT{Q}_n-F$ satisfies one of the conditions (1)-(7) in Lemma 10.

Case 3. $4n-13\le \left|F_0\right|\le 4n-10$ .

Since $4n-13\le \left|F_0\right|\le 4n-10$ and $\left|F\right|\le 4n-10$ , $\left|F_1\right|\le \left(4n-10\right)-\left(4n-13\right)=3$ . By Lemma 1, $1LT{Q}_{n-1}-F_1$ is connected.

Suppose that $0LT{Q}_{n-1}-F_0$ is connected. Since $2^{n-1}-\left(4n-10\right)\ge 1$ , by Le- mma 3, $LT{Q}_n-F$ is connected.

Suppose that $0LT{Q}_{n-1}-F_0$ is not connected. Let the components in

$0LT{Q}_{n-1}-F_0$ be $G_1,G_2,\cdots ,G_k$ for $k\ge 2$ and $\left|V\left(G_1\right)\right|\le \left|V\left(G_2\right)\right|\le \cdots \le \left|V\left(G_k\right)\right|$ . If $\left|V\left(G_r\right)\right|\ge 4\left(1\le r\le k-1\right)$ , by Lemma 3, $\left|N\left(V\left(G_r\right)\right)\cap V\left(1LT{Q}_{n-1}\right)\right|\ge 4$ . Combining this with $\left|F_1\right|\le \left(4n-10\right)-\left(4n-13\right)=3$ , we have that $LT{Q}_n\left[V\left(G_r\right)\cup V\left(1LT{Q}_{n-1}-F_1\right)\right]$ is connected. Therefore, $G_r$ is not a com- ponent of $LT{Q}_n-F$ for $\left|V\left(G_r\right)\right|\ge 4$ . Therefore, $LT{Q}_n-F$ is connected. The following we discuss $G_r$ is a component of $LT{Q}_n-F$ with $\left|V\left(G_r\right)\right|\le 3\left(1\le r\le k-1\right)$ .

If $k=5$ , by Lemma 3, $\left|N\left(V\left(G_1\right)\right)\cup N\left(V\left(G_2\right)\right)\cup \cdots \cup N\left(V\left(G_{k-1}\right)\right)\cap V\left(1LT{Q}_{n-1}\right)\right|\ge 4$ . Combining this with $\left|F_1\right|\le 3$ , there is one $G_r\left(1\le r\le k-1\right)$ such that $LT{Q}_n\left[V\left(G_r\right)\cup V\left(1LT{Q}_{n-1}-F_1\right)\right]$ is connected. Thus, $k\le 4$ . Since $\left|F_1\right|\le 3$ , $\left|V\left(G_r\right)\right|\le 3\left(1\le r\le k-1\right)$ and $k\le 4$ , $LT{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 $\left|F\right|$ super g-extra connected.

Theorem 9. Let $LT{Q}_n$ be the locally twisted cube for $n\ge 6$ . Then $LT{Q}_n$ is tightly $\left(4n-9\right)$ super 3-extra connected.

Proof. By Theorem 8, we know for any minimum 3-extra cut $F\subset V\left(LT{Q}_n\right)$ , $\left|F\right|=4n-9$ . We decompose $LT{Q}_n$ into $0LT{Q}_{n-1}$ and $1LT{Q}_{n-1}$ . Then $0LT{Q}_{n-1}$ and $1LT{Q}_{n-1}$ are isomorphic to $LT{Q}_{n-1}$ . Suppose that

$F_i=F\cap V\left(iLT{Q}_{n-1}\right)$ , $i\in \left\{\mathrm{0,1}\right\}$ . Without loss of generality, let $\left|F_0\right|\ge \left|F_1\right|$ . And

since $\left|F\right|=4n-9$ , $2n-4\le \lceil \frac{4n-9}{2}\rceil \le \left|F_0\right|\le 4n-9$ , $0\le \left|F_1\right|\le \lfloor \frac{4n-9}{2}\rfloor \le 2n-5$ .

Let $C_i$ be the maximum component of $iLT{Q}_{n-1}-F_i$ , $i\in \left\{\mathrm{0,1}\right\}$ . We consider the following cases.

Case 1. $2n-4\le \left|F_0\right|\le 3\left(n-1\right)-6=3n-9$ .

Since $\left|F_0\right|\ge \left|F_1\right|$ and $\left|F\right|=4n-9$ , $\left|F_1\right|\le 2n-5$ holds.

By Lemmas 1 and 2, $1LT{Q}_{n-1}-F_1$ is connected or has two components, one of which is an isolated vertex. Since $2n-4\le \left|F_0\right|\le 3\left(n-1\right)-6=3n-9$ , by lemma 8, $0LT{Q}_{n-1}-F_0$ satisfies one of the following conditions: 1) $0LT{Q}_{n-1}-F_0$ has three components, two of which are isolated vertices; 2) $0LT{Q}_{n-1}-F_0$ has two components, one of which is an isolated vertex; 3) $0LT{Q}_{n-1}-F_0$ has two com- ponents, one of which is a $K_2$ ; 4) $0LT{Q}_{n-1}-F_0$ is connected. Since $2^{n-1}-\left(4n-9\right)-3\ge 1$ , by Lemma 3, $LT{Q}_n\left[V\left(C_0\right)\cup V\left(C_1\right)\right]$ is connected. Then $LT{Q}_n-F$ satisfies one of the following conditions:

1) $LT{Q}_n-F$ has four components, three of which are isolated vertices;

2) $LT{Q}_n-F$ has three components, one of which is isolated vertices and one of which is a $K_2$ ;

3) $LT{Q}_n-F$ has three components, two of which are isolated vertices;

4) $LT{Q}_n-F$ has two components, one of which is a path of length two;

5) $LT{Q}_n-F$ has two components, one of which is an isolated vertex;

6) $LT{Q}_n-F$ has two components, one of which is a $K_2$ ;

7) $LT{Q}_n-F$ is connected.

Thus, in this case, F is not a minimum 3-extra cut of $LT{Q}_n$ , a contradiction.

Case 2. $\left|F_0\right|=3n-8$ .

Since $\left|F_0\right|=3n-8$ and $\left|F\right|=4n-9$ , we have $\left|F_1\right|=\left(4n-9\right)-\left(3n-8\right)=n-1$ . By Lemmas 1 and 2, $1LT{Q}_{n-1}-F_1$ is connected or has two components, one of which is an isolated vertex. Since $\left|F_0\right|=3n-8$ , by Lemma 10, $0LT{Q}_{n-1}-F_0$ satisfies one of the following conditions:

1) $0LT{Q}_{n-1}-F_0$ has four components, three of which are isolated vertices;

2) $0LT{Q}_{n-1}-F_0$ has three components, one of which is isolated vertices and the other of which is a $K_2$ ;

3) $0LT{Q}_{n-1}-F_0$ has three components, two of which are isolated vertices;

4) $0LT{Q}_{n-1}-F_0$ has two components, one of which is a path of length two;

5) $0LT{Q}_{n-1}-F_0$ has two components, one of which is an isolated vertex;

6) $0LT{Q}_{n-1}-F_0$ has two components, one of which is a $K_2$ ;

7) $0LT{Q}_{n-1}-F_0$ is connected.

If $0LT{Q}_{n-1}-F_0$ satisfies the condition (4), i.e., $0LT{Q}_{n-1}-F_0$ has two com- ponents, one of which is a path of length two, denoted by $P=uvw$ , $1LT{Q}_{n-1}-F_1$ has two components, one of which is an isolated vertex x, and $\left|N\left(x\right)\cap V\left(P\right)\right|=1$ , $\left(N\left(V\left(P\right)\right)\cap V\left(1LT{Q}_{n-1}\right)\right)\backslash \left\{x\right\}\subseteq F_1$ , then, by Lemma 3, $LT{Q}_n-F$ has one component which is a 3-path or a $K_{\mathrm{1,3}}$ . Since $2^{n-1}-\left(4n-9\right)-3\ge 1$ for $n\ge 6$ , $LT{Q}_n\left[C_0\cup C_1\right]$ is connected. Thus, $LT{Q}_n-F$ exactly has two components. Then the other component C satisfies $\left|C\right|=2^n-\left(4n-9\right)-4>4$ for $n\ge 6$ . Otherwise, F is not a minimum 3-extra cut of $LT{Q}_n$ , a contradiction.

Case 3. $3n-7\le \left|F_0\right|\le 4n-14$ .

Since $\left|F_0\right|\ge \left|F_1\right|$ and $\left|F\right|\le 4n-9$ , $\left|F_1\right|\le \left(4n-9\right)-\left(3n-7\right)=n-2$ . By Le- mma 1, $1LT{Q}_{n-1}-F_1$ is connected. Since $3n-7\le \left|F_0\right|\le 4n-14$ , by Lemma 10, $0LT{Q}_{n-1}-F_0$ satisfies one of the following conditions:

1) $0LT{Q}_{n-1}-F_0$ has four components, three of which are isolated vertices;

2) $0LT{Q}_{n-1}-F_0$ has three components, one of which is isolated vertices and the other of which is a $K_2$ ;

3) $0LT{Q}_{n-1}-F_0$ has three components, two of which are isolated vertices;

4) $0LT{Q}_{n-1}-F_0$ has two components, one of which is a path of length two;

5) $0LT{Q}_{n-1}-F_0$ has two components, one of which is an isolated vertex;

6) $0LT{Q}_{n-1}-F_0$ has two components, one of which is a $K_2$ ;

7) $0LT{Q}_{n-1}-F_0$ is connected.

Thus, $LT{Q}_n-F$ satisfies one of the following conditions:

1) $LT{Q}_n-F$ has four components, three of which are isolated vertices;

2) $LT{Q}_n-F$ has three components, one of which is isolated vertices and one of which is a $K_2$ ;

3) $LT{Q}_n-F$ has three components, two of which are isolated vertices;

4) $LT{Q}_n-F$ has two components, one of which is a path of length two;

5) $LT{Q}_n-F$ has two components, one of which is an isolated vertex;

6) $LT{Q}_n-F$ has two components, one of which is a $K_2$ ;

7) $LT{Q}_n-F$ is connected.

In this case, F is not a minimum 3-extra cut of $LT{Q}_n$ , a contradiction.

Case 4. $\left|F_0\right|=4n-13$ .

Since $\left|F_0\right|=4n-13$ and $\left|F\right|=4n-9$ for $n\ge 6$ , $\left|F_1\right|=\left(4n-9\right)-\left(4n-13\right)=4$ . By Lemma 1, $1LT{Q}_{n-1}-F_1$ is connected.

If there exists a 3-path P in $0LT{Q}_{n-1}-F_0$ , then $N\left(V\left(P\right)\right)\cap V\left(0LT{Q}_{n-1}\right)\subseteq F_0$ . By Corollary 1, $\left|N\left(V\left(P\right)\right)\right|\ge 4n-13=\left|F_0\right|$ in $0LT{Q}_{n-1}-F_0$ . Therefore, $N\left(V\left(P\right)\right)=F_0$ in $0LT{Q}_{n-1}-F_0$ . Note that $2^{n-1}-\left(4n-9\right)-4\ge 1$ for $n\ge 6$ , by Lemma 3, then $LT{Q}_n\left[V\left(C_0\right)\cup V\left(C_1\right)\right]$ is connected. Then $LT{Q}_n-F$ just has two components, one of which is a 3-path.

If there exists a component $K_{\mathrm{1,3}}$ in $0LT{Q}_{n-1}-F_0$ , then $N_{0LT{Q}_{n-1}}\left(V\left(K_{\mathrm{1,3}}\right)\right)\subseteq F_0$ . By Corollary 1, $\left|N\left(V\left(K_{1,3}\right)\right)\right|\ge 4n-13=\left|F_0\right|$ in $0LT{Q}_{n-1}-F_0$ . Therefore, $N\left(V\left(K_{1,3}\right)\right)=F_0$ in $0LT{Q}_{n-1}-F_0$ . Note that $2^{n-1}-\left(4n-9\right)-4\ge 1$ for $n\ge 6$ , by Lemma 3, $LT{Q}_n-F$ just has two com- ponents, one of which is a $K_{\mathrm{1,3}}$ .

If there exists a 4-cycle C in $0LT{Q}_{n-1}-F_0$ , then $N_{0LT{Q}_{n-1}}\left(C\right)\cap V\left(0LT{Q}_{n-1}\right)\subseteq F_0$ . By Proposition 7, $\left|N_{0LT{Q}_{n-1}}\left(V\left(C\right)\right)\right|\ge 4\left(n-1-2\right)=4n-12>4n-13=\left|F_0\right|$ , a contradiction to $\left|F_0\right|=4n-13$ . Therefore, $0LT{Q}_{n-1}-F_0$ has not a 4-cycle.

Case 5. $4n-12\le \left|F_0\right|\le 4n-9$ .

Since $4n-12\le \left|F_0\right|\le 4n-9$ and $\left|F\right|\le 4n-9$ , $\left|F_1\right|\le \left(4n-9\right)-\left(4n-12\right)=3$ . By Lemma 1, $1LT{Q}_{n-1}-F_1$ is connected.

Suppose that $0LT{Q}_{n-1}-F_0$ is connected. Since $2^{n-1}-\left(4n-9\right)\ge 1$ , by Le- mma 3, $LT{Q}_n-F$ is connected, a contradiction.

Suppose that $0LT{Q}_{n-1}-F_0$ is not connected. Let the components in $0LT{Q}_{n-1}-F_0$ be $G_1,G_2,\cdots ,G_k$ for $k\ge 2$ and $\left|V\left(G_1\right)\right|\le \left|V\left(G_2\right)\right|\le \cdots \le \left|V\left(G_k\right)\right|$ . If $\left|V\left(G_r\right)\right|\ge 4\left(1\le r\le k-1\right)$ , by Lemma 3, $\left|N\left(V\left(G_r\right)\right)\cap V\left(1LT{Q}_{n-1}\right)\right|\ge 4$ . If $k\ge 5$ , by Lemma 3, $\left|N\left(V\left(G_1\right)\right)\cup N\left(V\left(G_2\right)\right)\cup \dots \cup N\left(V\left(G_{k-1}\right)\right)\cap V\left(1LT{Q}_{n-1}\right)\right|\ge 4$ . Combining this with $\left|F_1\right|\le \left(4n-9\right)-\left(4n-12\right)=3$ , we have that $LT{Q}_n-F$ satisfies one of the following conditions:

1) $LT{Q}_n-F$ has four components, three of which are isolated vertices;

2) $LT{Q}_n-F$ has three components, one of which is isolated vertices and one of which is a $K_2$ ;

3) $LT{Q}_n-F$ has three components, two of which are isolated vertices;

4) $LT{Q}_n-F$ has two components, one of which is a path of length two;

5) $LT{Q}_n-F$ has two components, one of which is an isolated vertex;

6) $LT{Q}_n-F$ has two components, one of which is a $K_2$ ;

7) $LT{Q}_n-F$ is connected.

In this case, F is not a minimum 3-extra cut of $LT{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=\left(V,E\right)$ is g-extra t-diagnosable under the PMC model if and only if there is an edge $uv\in E$ with $u\in V\backslash \left(F_1\cup F_2\right)$ and $v\in F_1\Delta F_2$ for each distinct pair of g-extra faulty sub- sets $F_1$ and $F_2$ of V with $\left|F_1\right|\le t$ and $\left|F_2\right|\le t$ .

Lemma 11. Let $n\ge 4$ . Then the 3-extra diagnosability of the locally twisted cube $LT{Q}_n$ under the PMC model is less than or equal to $4n-6$ , i.e., ${\tilde{t}}_3\left(LT{Q}_n\right)\le 4n-6$ .

Proof. Let A be defined in Lemma 7, and let $F_1=N_{LT{Q}_n}\left(A\right)$ , $F_2=A\cup N_{LT{Q}_n}\left(A\right)$ . By Lemma 7, $\left|F_1\right|=4n-9$ , $\left|F_2\right|=\left|A\right|+\left|F_1\right|=4n-5$ , $\left|V\left(LT{Q}_n\left[A\right]\right)\right|\ge 4$ and $\left|V\left(LT{Q}_n-F_2\right)\right|\ge 4$ , $F_1$ is a 3-extra cut of $LT{Q}_n$ . Therefore, $F_1$ and $F_2$ are 3-extra faulty sets of $LT{Q}_n$ with $\left|F_1\right|=4n-9$ and $\left|F_2\right|=4n-5$ . Since $A=F_1\Delta F_2$ and $N_{LT{Q}_n}\left(A\right)=F_1\subset F_2$ , there is no edge of $LT{Q}_n$ between $V\left(LT{Q}_n\right)\backslash \left(F_1\cup F_2\right)$ and $F_1\Delta F_2$ . By Theorem 10, we can deduce that $LT{Q}_n$ is not 3-extra $\left(4n-5\right)$ -diagnosable under PMC model. Hence, by the definition of 3-extra diagnosability, we conclude that the 3-extra diagnosability of $LT{Q}_n$ is less than $4n-5$ , i.e., ${\tilde{t}}_3\left(LT{Q}_n\right)\le 4n-6$ .

Lemma 12. Let $n\ge 5$ . Then the 3-extra diagnosability of the locally twisted cube $LT{Q}_n$ under the PMC model is more than or equal to $4n-6$ , i.e., ${\tilde{t}}_3\left(LT{Q}_n\right)\ge 4n-6$ .

Proof. By the definition of 3-extra diagnosability, it is sufficient to show that $LT{Q}_n$ is 3-extra $\left(4n-6\right)$ -diagnosable. By Theorem 10, to prove $LT{Q}_n$ is 3- extra $\left(4n-6\right)$ -diagnosable, it is equivalent to prove that there is an edge $uv\in E\left(LT{Q}_n\right)$ with $u\in V\left(LT{Q}_n\right)\backslash \left(F_1\cup F_2\right)$ and $v\in F_1\Delta F_2$ for each distinct pair of 3-extra faulty subsets $F_1$ and $F_2$ of $V\left(LT{Q}_n\right)$ with $\left|F_1\right|\le 4n-6$ and $\left|F_2\right|\le 4n-6$ .

Suppose, by way of contradiction, that there are two distinct 3-extra faulty subsets $F_1$ and $F_2$ of $LT{Q}_n$ with $\left|F_1\right|\le 4n-6$ and $\left|F_2\right|\le 4n-6$ , but the vertex set pair $\left(F_1\mathrm{,}{F}_2\right)$ is not satisfied with the condition in Theorem 10, i.e., there are no edges between $V\left(LT{Q}_n\right)\backslash \left(F_1\cup F_2\right)$ and $F_1\Delta F_2$ . Without loss of generality, assume that $F_2\backslash F_1\ne \varnothing$ .

Assume $V\left(LT{Q}_n\right)=F_1\cup F_2$ . Since $n\ge 5$ , we have that $2^n=\left|V\left(LT{Q}_n\right)\right|=$ $\left|F_1\cup F_2\right|=\left|F_1\right|+\left|F_2\right|-\left|F_1\cap F_2\right|\le \left|F_1\right|+\left|F_2\right|\le \left(4n-6\right)+\left(4n-6\right)=8n-12$ , a contra- diction. Therefore, $V\left(LT{Q}_n\right)\ne F_1\cup F_2$ .

The following we discuss the case when $F_2\backslash F_1\ne \varnothing$ and $V\left(LT{Q}_n\right)\ne F_1\cup F_2$ .

Since there are no edges between $V\left(LT{Q}_n\right)\backslash \left(F_1\cup F_2\right)$ and $F_1\Delta F_2$ , and $F_1$ is a 3-extra faulty set, $LT{Q}_n-F_1$ has two parts $LT{Q}_n-F_1-F_2$ and $LT{Q}_n\left[F_2\backslash F_1\right]$ . Thus, every component $G_i$ of $LT{Q}_n-F_1-F_2$ satisfies $\left|V\left(G_i\right)\right|\ge 4$ and every component $C_i$ of $LT{Q}_n\left[F_2\backslash F_1\right]$ satisfies $\left|V\left(C_i\right)\right|\ge 4$ . Similarly, every component ${C^{\prime }}_i$ of $LT{Q}_n\left[F_1\backslash F_2\right]$ satisfies $\left|V\left({C^{\prime }}_i\right)\right|\ge 4$ when $F_1\backslash F_2\ne \varnothing$ . Therefore, $F_1\cap F_2$ is also a 3-extra faulty set. Since there are no edges between $V\left(LT{Q}_n-F_1-F_2\right)$ and $F_1\Delta F_2$ , $F_1\cap F_2$ is also a 3-extra cut. When $F_1\backslash F_2=\varnothing$ , $F_1\cap F_2=F_1$ is also a 3-extra faulty set. Since there are no edges between $V\left(LT{Q}_n-F_1-F_2\right)$ and $F_1\Delta F_2$ , $F_1\cap F_2$ is a 3-extra cut. By Theorem 8, $\left|F_1\cap F_2\right|\ge 4n-9$ . Therefore, $\left|F_2\right|=\left|F_2\backslash F_1\right|+\left|F_1\cap F_2\right|\ge 4+4n-9=4n-5$ , which contradicts with that $\left|F_2\right|\le 4n-6$ . So $LT{Q}_n$ is 3-extra $\left(4n-6\right)$ -diagnosable. By the definition of ${\tilde{t}}_3\left(LT{Q}_n\right)$ , ${\tilde{t}}_3\left(LT{Q}_n\right)\ge 4n-6$ . The proof is complete.

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

Theorem 11. Let $n\ge 5$ . Then the 3-extra diagnosability of the locally twisted cubes $LT{Q}_n$ under the PMC model is $4n-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 $LT{Q}_n$ under the MM^* model, we first give an existing result.

Theorem 12 ( [3] [16] [26] ) A system $G=\left(V,E\right)$ 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 $\left|F_1\right|\le t$ and $\left|F_2\right|\le t$ satisfies one of the following conditions.

1) There are two vertices $u\mathrm{,}w\in V\backslash \left(F_1\cup F_2\right)$ and there is a vertex $v\in F_1\Delta F_2$ such that $uw\in E$ and $vw\in E$ .

2) There are two vertices $u\mathrm{,}v\in F_1\backslash F_2$ and there is a vertex $w\in V\backslash \left(F_1\cup F_2\right)$ such that $uw\in E$ and $vw\in E$ .

3) There are two vertices $u\mathrm{,}v\in F_2\backslash F_1$ and there is a vertex $w\in V\backslash \left(F_1\cup F_2\right)$ such that $uw\in E$ and $vw\in E$ .

Lemma 13. Let $n\ge 4$ . Then the 3-extra diagnosability of the locally twisted cube $LT{Q}_n$ under the MM^* model is less than or equal to $4n-6$ , i.e., ${\tilde{t}}_3\left(LT{Q}_n\right)\le 4n-6$ .

Proof. Let A be defined in Lemma 7, and let $F_1=N_{LT{Q}_n}\left(A\right)$ , $F_2=A\cup N_{LT{Q}_n}\left(A\right)$ . By Lemma 7, $\left|F_1\right|=4n-9$ , $\left|F_2\right|=\left|A\right|+\left|F_1\right|=4n-5$ , $\left|V\left(LT{Q}_n\left[A\right]\right)\right|\ge 4$ and $\left|V\left(LT{Q}_n-F_2\right)\right|\ge 4$ , $F_1$ is a 3-extra cut of $LT{Q}_n$ . Therefore, $F_1$ and $F_2$ are 3-extra faulty sets of $LT{Q}_n$ with $\left|F_1\right|=4n-9$ and $\left|F_2\right|=4n-5$ . Since $A=F_1\Delta F_2$ and $N_{LT{Q}_n}\left(A\right)=F_1\subset F_2$ , there is no edge of $LT{Q}_n$ between $V\left(LT{Q}_n\right)\backslash \left(F_1\cup F_2\right)$ and $F_1\Delta F_2$ . By Theorem 12, we can deduce that $LT{Q}_n$ is not 3-extra $\left(4n-5\right)$ -diagnosable under MM^* model. Hence, by the definition of 3-extra diagnosability, we conclude that the 3-extra diagnosability of $LT{Q}_n$ is less than $4n-5$ , i.e., ${\tilde{t}}_3\left(LT{Q}_n\right)\le 4n-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\left(G\right)$ the number of odd components of G.

Lemma 14. ( [20] ) A graph $G=\left(V,E\right)$ has a perfect matching if and only if $o\left(G-S\right)\le \left|S\right|$ for all $S\subseteq V$ .

Lemma 15. Let $n\ge 7$ . Then the 3-extra diagnosability of the locally twisted cube $LT{Q}_n$ under the MM^* model is more than or equal to $4n-6$ , i.e., ${\tilde{t}}_3\left(LT{Q}_n\right)\ge 4n-6$ .

Proof. By the definition of the 3-extra diagnosability, it is sufficient to show that $LT{Q}_n$ is 3-extra $\left(4n-6\right)$ -diagnosable.

By Theorem 12, suppose, by way of contradiction, that there are two distinct 3-extra faulty subsets $F_1$ and $F_2$ of $LT{Q}_n$ with $\left|F_1\right|\le 4n-6$ and $\left|F_2\right|\le 4n-6$ , but the vertex set pair $\left(F_1\mathrm{,}{F}_2\right)$ is not satisfied with any one condition in Theorem 12. Without loss of generality, assume that $F_2\backslash F_1\ne \varnothing$ . Similarly to the discussion on $V\left(LT{Q}_n\right)=F_1\cup F_2$ in Lemma 12, we can deduce $V\left(LT{Q}_n\right)\ne F_1\cup F_2$ . Therefore, we have the following discussion for $V\left(LT{Q}_n\right)\ne F_1\cup F_2$ .

Claim 1. $LT{Q}_n-F_1-F_2$ has no isolated vertex.

Suppose, by way of contradiction, that $LT{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\in F_2\backslash F_1$ such that u are adjacent to w. Since the vertex set pair $\left(F_1\mathrm{,}{F}_2\right)$ is not satisfied with any one condition in Theorem 12, by the condition (3) of Theorem 12, there is at most one vertex $u\in F_2\backslash F_1$ such that u is adjacent to w. Therefore, there is just a vertex u is adjacent to w.

Case 1. $F_1\backslash F_2=\varnothing$ .

If $F_1\backslash F_2=\varnothing$ , then $F_1\subseteq F_2$ . Since $F_2$ is a 3-extra faulty set, every com- ponent $G_i$ of $LT{Q}_n-F_1-F_2$ has $\left|V\left(G_i\right)\right|\ge 4$ . Thus, $LT{Q}_n-F_1-F_2$ has no isolated vertex.

Case 2. $F_1\backslash F_2\ne \varnothing$ .

Similarly, since $F_1\backslash F_2\ne \varnothing$ , by the condition (2) of Theorem 12 and the hypothesis, we can deduce that there is just a vertex $v\in F_1\backslash F_2$ such that v is adjacent to w.

Let $W\subseteq V\left(LT{Q}_n\right)\backslash \left(F_1\cup F_2\right)$ be the set of isolated vertices in $LT{Q}_n\left[V\left(LT{Q}_n\right)\backslash \left(F_1\cup F_2\right)\right]$ , and H be the induced subgraph by the vertex set $V\left(LT{Q}_n\right)\backslash \left(F_1\cup F_2\cup W\right)$ . Then for any $w\in W$ , there are $\left(n-2\right)$ neighbors in $F_1\cap F_2$ . By Lemmas 14 and 3, $\left|W\right|\le o\left(LT{Q}_n-\left(F_1\cup F_2\right)\right)\le \left|F_1\cup F_2\right|=$ $\left|F_1\right|+\left|F_2\right|-\left|F_1\cap F_2\right|\le \left(4n-6\right)+\left(4n-6\right)-\left(n-2\right)=7n-10$ . Assume $V\left(H\right)=\varnothing$ . Then $2^n=\left|V\left(LT{Q}_n\right)\right|=\left|F_1\cup F_2\right|+\left|W\right|=\left|F_1\right|+\left|F_2\right|-\left|F_1\cap F_2\right|\le \left(4n-6\right)+$ $\left(4n-6\right)-\left(n-2\right)+\left(7n-10\right)=14n-20$ , a contradiction to that $n\ge 7$ . So $V\left(H\right)\ne \varnothing$ .

The following we discuss the case when $F_1\backslash F_2\ne \varnothing$ , $F_2\backslash F_1\ne \varnothing$ and $V\left(H\right)\ne \varnothing$ .

Since the vertex set pair $\left(F_1\mathrm{,}{F}_2\right)$ 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\left(H\right)$ and $F_1\Delta F_2$ . Note that $F_2\backslash F_1\ne \varnothing$ . If $F_1\cap F_2=\varnothing$ , then this is a contradiction to that $LT{Q}_n$ is connected. Therefore, $F_1\cap F_2\ne \varnothing$ . Thus, $F_1\cap F_2$ is a vertex cut of $LT{Q}_n$ . Since $F_1$ is a 3-extra faulty set of $LT{Q}_n$ , we have that every component $H_i$ of H has $\left|V\left(H_i\right)\right|\ge 4$ and every component $C_i$ of $LT{Q}_n\left[W\cup \left(F_2\backslash F_1\right)\right]$ has $\left|V\left(C_i\right)\right|\ge 4$ . Since $F_2$ also is a 3-extra faulty set of $LT{Q}_n$ , we have that every component ${C^{\prime }}_i$ of $LT{Q}_n\left[W\cup \left(F_1\backslash F_2\right)\right]$ has $\left|V\left({C^{\prime }}_i\right)\right|\ge 4$ . Note that $LT{Q}_n-\left(F_1\cap F_2\right)$ has two parts: H and $LT{Q}_n\left[W\cup \left(F_1\Delta F_2\right)\right]$ . Let $b_i\in V\left(LT{Q}_n\left[W\cup \left(F_1\Delta F_2\right)\right]\right)$ . If $b_i\in W$ , then $b_i$ has two neighbors $u\in V\left(C_i\right)$ and $v\in V\left({C^{\prime }}_i\right)$ . Then $b_i\in V\left(C_i\cup {C^{\prime }}_i\right)$ and $\left|V\left(C_i\cup {C^{\prime }}_i\right)\right|\ge 4$ . Thus, $F_1\cap F_2$ is a 3-extra cut of $LT{Q}_n$ . By Theorem 8, $\left|F_1\cap F_2\right|\ge 4n-9$ . Since $\left|V\left(C_i\right)\right|\ge 4$ , $\left|F_2\backslash F_1\right|\ge 3$ . Since $\left|F_1\cap F_2\right|=\left|F_2\right|-\left|F_2\backslash F_1\right|\le \left(4n-6\right)-3=4n-9$ , we have $\left|F_1\cap F_2\right|=4n-9$ . Then $\left|F_2\backslash F_1\right|=3$ and $\left|F_2\right|=4n-6$ . Similarly, $\left|F_1\backslash F_2\right|=3$ , $\left|F_1\right|=4n-6$ . By Lemma 9, the locally twisted cube $LT{Q}_n$ is tightly $\left(4n-9\right)$ super 3-extra connected, i.e., $LT{Q}_n-\left(F_1\cap F_2\right)$ has two components, one of which is a subgraph of or- der 4. Noted that $\left|W\right|\le 7n-10$ . $2^n=\left|V\left(LT{Q}_n\right)\right|=\left|F_1\backslash F_2\right|+\left|F_2\backslash F_1\right|+\left|F_1\cap F_2\right|+$ $\left|V\left(H\right)\right|+\left|W\right|\le 3+3+\left(4n-9\right)+4+\left(7n-10\right)=11n-9$ , a contradiction to $n\ge 7$ . Therefore, $LT{Q}_n-F_1-F_2$ has no isolated vertex when $F_1\backslash F_2\ne \varnothing$ , $F_2\backslash F_1\ne \varnothing$ and $V\left(H\right)\ne \varnothing$ . The proof of Claim 1 is complete.

Let $u\in V\left(LT{Q}_n\right)\backslash \left(F_1\cup F_2\right)$ . By Claim 1, u has at least one neighbor vertex in $LT{Q}_n-F_1-F_2$ . Since the vertex set pair $\left(F_1\mathrm{,}{F}_2\right)$ is not satisfied with any one condition in Theorem 12, by the condition (1) of Theorem 12, for any pair of adjacent vertices $u\mathrm{,}w\in V\left(LT{Q}_n\right)\backslash \left(F_1\cup F_2\right)$ , there is no vertex $v\in F_1\Delta F_2$ such that $uw\in E\left(LT{Q}_n\right)$ and $uv\in E\left(LT{Q}_n\right)$ . It follows that u has no neighbor vertex in $F_1\Delta F_2$ . By the arbitrariness of u, there is no edge between $V\left(LT{Q}_n\right)\backslash \left(F_1\cup F_2\right)$ and $F_1\Delta F_2$ . Since $F_2\backslash F_1\ne \varnothing$ and $F_1$ is a 3-extra faulty set, $\left|F_2\backslash F_1\right|\ge 4$ and $\left|V\left(LT{Q}_n-F_2-F_1\right)\right|\ge 4$ . Since $F_1$ also is 3-extra faulty sets, $\left|F_1\backslash F_2\right|\le 4$ and $\left|V\left(LT{Q}_n-F_1-F_2\right)\right|\ge 4$ . Then $F_1\cap F_2$ is a 3- extra cut of $LT{Q}_n$ . By Theorem 8, we have $\left|F_1\cap F_2\right|\ge 4n-9$ . Therefore, $\left|F_2\right|=\left|F_2\backslash F_1\right|+\left|F_1\cap F_2\right|\ge 4+\left(4n-9\right)=4n-5$ , which contradicts $\left|F_2\right|\le 4n-6$ . Therefore, $LT{Q}_n$ is 3-extra $\left(4n-6\right)$ -diagnosable and ${\tilde{t}}_3\left(LT{Q}_n\right)\ge 4n-6$ . The proof is complete.

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

Theorem 13. Let $n\ge 7$ . Then the 3-extra diagnosability of the locally twisted cube $LT{Q}_n$ under the MM^* model is $4n-6$ .

Acknowledgements

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

Cite this paper

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

References