Conditional Edge Connectivity of the Locally Twisted Cubes

Abstract

The k-component edge connectivity $c\lambda _{k}(G)$ of a non-complete graph G is the minimum number of edges whose deletion results in a graph with at least k components. In this paper, we extend some results by Guo et al. (Appl Math Comput 334:401–406, 2018) by determining the component edge connectivity of the locally twisted cubes $\mathrm{LTQ}_{n}$, i.e., $c\lambda _{k+1}(\mathrm{LTQ}_{n})=kn-\frac{ex_{k}}{2}$ for $1\leqslant k\leqslant 2^{[\frac{n}{2}]}$, $n\geqslant 7$, where $ex_{k}=\sum _{i=0}^{s}t_{i}2^{t_{i}}+\sum _{i=0}^{s}2\cdot i\cdot 2^{t_{i}}$, and k is a positive integer with decomposition $k=\sum _{i=0}^{s}2^{t_{i}}$ such that $t_{0}=\lfloor \mathrm{log}_{2}k\rfloor$ and $t_{i}=\lfloor \mathrm{log}_{2}(k-\sum _{r=0}^{i-1}2^{t_{r}})\rfloor$ for $i\geqslant 1$. As a by-product, we characterize the corresponding optimal solutions.

1 Introduction

Fault tolerance concerns the capability of an interconnection network to transmit messages; it is a very important property to study. In general, the network structure is modeled as graphs, and the properties of the network can be evaluated by the parameters of the graphs. There are many parameters that have been introduced to measure the reliability of a network structure. Perhaps, edge connectivity $\lambda (G)$ of a graph G is the most important one. The larger the edge connectivity is, the more reliable the interconnection network is.

However, this criterion has its shortcoming: The further properties of disconnected components are not depicted. Under this consideration, Harary [2] introduced the concept of conditional connectivity by attaching some conditions on connected components and Latifi et al. [3] generalized the concept conditional connectivity by introducing restrictedh-connectivity. The concept considered here is slightly different from theirs.

As a natural extension of traditional edge connectivity $\lambda (G)$, Sampathkumar [4] proposed the concept of component edge connectivity. Let G be a non-complete graph. A k-component edge cut of G is a set of edges whose deletion results in a graph with at least k components. The k-component edge connectivity$c\lambda _{k}(G)$ of a graph G is the size of the smallest k-component edge cut of G. Obviously, $\lambda (G)=c\lambda _{2}(G)\leqslant c\lambda _{3}(G)\leqslant \cdots \leqslant c\lambda _{k}(G)$.

In recent years, as we know, the k-component edge connectivity has been studied for several famous networks (hypercubes $Q_{n}$, folded hypercubes $\hbox {FQ}_{n}$, twisted cubes $\mathrm{TN}_{n}$) in [1, 5,6,7]. Very recently, Guo et al. [1] determined $c\lambda _{k}(\mathrm{LTQ}_{n})$ of the locally twisted cubes $\mathrm{LTQ}_{n}$ for $k\leqslant 4$. In this paper, we extend their results by determining $c\lambda _{k}(\mathrm{LTQ}_{n})$ for $k\leqslant 2^{[\frac{n}{2}]}$.

The rest of the paper is organized as follows: In Sect. 2, we introduce some preliminary knowledge. In Sect. 3, we give the main result of this paper.

2 Preliminaries

For graph-theoretical terminology and notation not mentioned here, we follow [8]. Let $G=(V, E)$ be a graph. For each node $u\in V$, the neighborhood of u in a subgraph $H\subseteq G$, denoted by $N_{H}(u)$, is defined as the set of all nodes adjacent to u in H, and $d_{H}(u)=|N_{H}(u)|$ is the degree of u in H. We simply denote $N_{H}(u)=N(u)$ if $H=G$. For a node subset $S\subseteq V$, G[S] (resp. $G-S$) denotes the subgraph of G induced by the node set S (resp. $V-S$), and $E_{S}$ denotes the set of edges in which each edge contains exactly one end node in S. Similarly, for an edge subset $F\subseteq E$, $G-F$ denotes the subgraph of G induced by the edge set $E-F$. Let “$\oplus$” represent the modulo 2 addition.

Definition 2.1

[9] For an integer $n\geqslant 2$, the locally twisted cubes $\mathrm{LTQ}_{n}$ with node set $\{0,1\}^{n}$ were introduced by Yang et al. [9]. It can be defined recursively as follows: $\mathrm{LTQ}_{2}$ is a 4-cycle with node set $\{00, 01, 10, 11\}$ and edge set $\{(00, 01), (01, 11), (11, 10), (10, 00)\}$. For $n\geqslant 3$, $\mathrm{LTQ}_{n}$ can be built from $0\mathrm{LTQ}_{n-1}$ and $1\mathrm{LTQ}_{n-1}$, where $0\mathrm{LTQ}_{n-1}$ (resp. $1\mathrm{LTQ}_{n-1}$) denotes the graph obtained from $\mathrm{LTQ}_{n-1}$ by prefixing the label of each node with 0 (resp. 1), according to the following rule. Connect each node $0x_{2}x_{3}\cdots x_{n}$ of $0\mathrm{LTQ}_{n-1}$ to the node $1(x_{2} \oplus x_{n})x_{3}\cdots x_{n}$ of $1\mathrm{LTQ}_{n-1}$ with an edge.

Locally twisted cubes $\mathrm{LTQ}_{2}$, $\mathrm{LTQ}_{3}$, $\mathrm{LTQ}_{4}$ are depicted in Fig. 1. Yang et al. [9] introduced the n-dimensional $(n\geqslant 2)$ two-twisted cubes $Q_{n, 2}$ and showed that $Q_{n, 2}$ is isomorphic to $Q_{n}$. On the basis of the concepts of $Q_{n, 2}$ and $Q_{n}$, the locally twisted cubes $\mathrm{LTQ}_{n}$ can also be defined as follows:

Definition 2.2

[9] The locally twisted cubes $\mathrm{LTQ}_{n}$ can be built from $Q_{n-1}$ and $Q_{n-1, 2}$ by the following steps:

• (1) Let $Q_{n-1}0$ be the graph obtained from $Q_{n-1}$ by suffixing the labels of all nodes with 0.

• (2) Let $Q_{n-1, 2}1$ be the graph obtained from $Q_{n-1, 2}$ by suffixing the labels of all nodes with 1.

• (3) Connect each node $x_{1}x_{2}\cdots x_{n-1}0$ of $Q_{n-1}0$ to the node $x_{1}x_{2}\cdots x_{n-1}1$ of $Q_{n-1, 2}1$ by an edge.

Fig. 1

Locally twisted cubes $\mathrm{LTQ}_{2}$, $\mathrm{LTQ}_{3}$ and $\mathrm{LTQ}_{4}$

As an attractive alternative to hypercubes $Q_{n}$, $\mathrm{LTQ}_{n}$ is a member of hypercube-like networks $\mathrm{HL}_{n}$, and has been studied for many years and found many good properties, see, for example, [10,11,12,13,14,15,16,17,18] and the references therein.

Each node $u\in V(\mathrm{LTQ}_{n})$ can be denoted by an n-bit binary string, i.e., $u=u_{n}u_{n-1}\cdots u_{1}$, and also can be represented by decimal number, i.e., $u=\sum _{i=1}^{n}u_{i}2^{i-1}$.

Let m be an integer and $\sum _{i=0}^{s}2^{t_{i}}$ be the decomposition of m such that $t_{0}=\lfloor \mathrm{log}_{2}m\rfloor$, and $t_{i}=\lfloor \mathrm{log}_{2}(m-\sum _{r=0}^{i-1}2^{t_{r}})\rfloor$ for $i\geqslant 1$. We denote by $\frac{ex_{m}}{2}$ the maximum size of the subgraph of $\mathrm{LTQ}_{n}$ induced by m nodes, i.e., $ex_{m}=$max$\{2|E(\mathrm{LTQ}_{n}[S])| : S\subseteq V(\mathrm{LTQ}_{n})\;\text{ and }\;|S|=m\}$ is the maximum possible sum of degrees of the nodes in the subgraph of $\mathrm{LTQ}_{n}$ induced by m nodes.

Zhang et al. [19] and Yang et al. [20] have proved the following important results.

Lemma 2.3

[19] Let S be a node subset of $\mathrm{LTQ}_{n}$, where $|S|=m$ and $m=\sum _{i=0}^{s}2^{t_{i}}$. Then, $ex_{m}(\mathrm{LTQ}_{n})=\sum _{i=0}^{s}t_{i}2^{t_{i}}+\sum _{i=0}^{s}2\cdot i\cdot 2^{t_{i}}$.

Lemma 2.4

[20] Let $1\leqslant i, j\leqslant 2^{n}$ and $i+j\leqslant 2^{n}$. Then, $ex_{i}+ex_{j}+2min\{i, j\}\leqslant ex_{i+j}$.

In the same paper, they introduced a method to pick a connected subgraph $G_{0}$ in $\mathrm{LTQ}_{n}$ such that $|V(G_{0})|=m=\sum _{i=0}^{s}2^{t_{i}}$ and $|E(G_{0})|=\frac{ex_{m}}{2}$. Take $(s+1)$$t_{i}$-dimensional sub-$\mathrm{LTQ}_{n}$ (we use the notation sub-$\mathrm{LTQ}_{n}$ for the lower dimensional $\mathrm{LTQ}_{n}$) for $i=0, 1,\cdots ,s$ as follows:

$$\begin{aligned} \begin{aligned}&\mathrm{LTQ}^{0}: \underbrace{X_{1}\cdots X_{t_{o}}}_{t_{0}}0\cdots 0, \\&\mathrm{LTQ}^{1}: \underbrace{\underbrace{X_{1}\cdots X_{t_{1}}}_{t_{1}}0\cdots 0}_{t_{0}}10\cdots 0, \\&\mathrm{LTQ}^{2}: \underbrace{\underbrace{X_{1}\cdots X_{t_{2}}}_{t_{2}}0\cdots 0}_{t_{1}}10\cdots 010\cdots 0, \\&\cdots .\\ \end{aligned} \end{aligned}$$

(2.1)

Note that $\mathrm{LTQ}^{0}$ is given and $\mathrm{LTQ}^{i}$ is taken from a $t_{i-1}$-dimensional sub-$\mathrm{LTQ}_{n}$ which is obtained from $\mathrm{LTQ}^{i-1}$ by changing the 0 of $(t_{i-1}+1)\textit{th}$-coordinate of $\mathrm{LTQ}^{i-1}$ to 1. Denote $G_{0}=\mathrm{LTQ}_{n}[V(\mathrm{LTQ}^{0})\cup \cdots \cup V(\mathrm{LTQ}^{s})]$. It is not difficult to count the number of edges of $G_{0}$ by considering the edges within $\mathrm{LTQ}^{i}$’s ($\frac{1}{2}\cdot \sum _{i=0}^{s}t_{i}2^{t_{i}}$) and the edges between $\mathrm{LTQ}^{i}$’s ($\frac{1}{2}\cdot \sum _{i=0}^{s}2\cdot i\cdot 2^{t_{i}}$).

Remark 1

Note that each $\mathrm{LTQ}^{i}$ is connected for $0\leqslant i\leqslant s$. Then, $G_{0}$ is connected.

3 Main Result

In this section, we extend Theorem 3.1 of Guo et al. [1] by determining $c\lambda _{k+1}(\mathrm{LTQ}_{n})$ for $k=1, 2,\cdots ,2^{[\frac{n}{2}]}$, $n\geqslant 7$.

Theorem 3.1

[1] $c\lambda _{3}(\mathrm{LTQ}_{n})=2n-1$, $c\lambda _{4}(\mathrm{LTQ}_{n})=3n-2$ for $n\geqslant 2$.

Lemma 3.2

[21] Let $S=\{0, 1,\cdots , m-1\}$ be a node subset of $Q_{n}$. Then, $|E(Q_{n}[S])|=\frac{ex_{m}(Q_{n})}{2}$, where $ex_{m}(Q_{n})=$max$\{2|E(Q_{n}[S])| : S\subseteq V(Q_{n})\;\text{ and }\;|S|=m\}$.

Lemma 3.3

Let S be a node subset of $\mathrm{LTQ}_{n}$, where $|S|=m$ and $m=\sum _{i=0}^{s}2^{t_{i}}$. Then, $|E_{S}|\geqslant nm-ex_{m}$. Moreover, the function $\xi (m)=nm-\frac{ex_{m}}{2}$ is strictly increasing (with respect to m) if $m\leqslant 2^{n-1}-1$.

Proof

By Lemma 2.3, we can immediately obtain $|E_{S}|\geqslant nm-ex_{m}$. Note that the inequality $\xi (m+1)-\xi (m)=n-(s+1)>0$ is equivalent to $s<n-1$. Since $m=\sum _{i=0}^{s}2^{t_{i}}\leqslant 2^{n-1}-1=2^{n-2}+2^{n-3}+\cdots +2^{1}+2^{0}$, $s<n-1$, which implies that $\xi (m)$ is strictly increasing for $m\leqslant 2^{n-1}-1$.

Note that $\mathrm{LTQ}_{n}$ is n-regular. Let $G_{0}$ be a subgraph of $\mathrm{LTQ}_{n}$ induced by m nodes. By Lemma 2.3, $|E(G_{0})|\leqslant \frac{ex_{m}}{2}$. Moreover, if $m\leqslant 2^{n-2}$, then one can pick the subgraph $G_{0}$ in an $(n-2)$-dimensional sub-$\mathrm{LTQ}_{n}$ such that $|E(G_{0})|=\frac{ex_{m}}{2}$. Thus, we have the following observation.

Observation

If $m\leqslant 2^{n-2}$, then $(n-2)m-ex_{m}\geqslant 0$.

Zhao et al. showed the following results in [6]:

Lemma 3.4

[6] Let q and $q_{i}$ be positive integers. If $q=\sum _{i=1}^{k}q_{i}$, then $\sum _{i=1}^{k}ex_{q_{i}}\leqslant ex_{q-k+1}$.

Lemma 3.5

$c\lambda _{k+1}(\mathrm{LTQ}_{n})\leqslant nk-\frac{ex_{k}}{2}$ for $k\leqslant 2^{n}$ and $n\geqslant 2$.

Proof

To show that $c\lambda _{k+1}(\mathrm{LTQ}_{n})\leqslant nk-\frac{ex_{k}}{2}$, it suffices to find an edge subset F of $\mathrm{LTQ}_{n}$ with $|F|=nk-\frac{ex_{k}}{2}$ such that $\mathrm{LTQ}_{n}-F$ is disconnected and has at least $k+1$ components.

Case 1.$k\leqslant 2^{n-1}$.

Let $S=\{0, 2,\cdots , 2k-2\}$ (or $S=\{1, 3,\cdots , 2k-1\}$) be a node subset of $\mathrm{LTQ}_{n}$ and $G_{0}=\mathrm{LTQ}_{n}[S]$. By Definition 2.2 and Lemma 3.2, it is clear that $G_{0}\subseteq Q_{n-1}0$ (or $G_{0}\subseteq Q_{n-1, 2}1$) and $|E(G_{0})|=\frac{ex_{k}}{2}$. Take $F=E(G_{0})\cup E_{V(G_{0})}$ which is required.

Case 2.$2^{n-1}<k\leqslant 2^{n}$.

Let $S=\{0, 2,\cdots , 2^{n}-2, 1, 3, \cdots ,2(k-2^{n-1})-1\}$ (or $S=\{1, 3,\cdots , 2^{n}-1, 0, 2,\cdots ,2(k-2^{n-1})-2\}$) be a node subset of $\mathrm{LTQ}_{n}$ and $G_{0}=\mathrm{LTQ}_{n}[S]$. Then, $G_{0}$ is the subgraph of $\mathrm{LTQ}_{n}$ in (2.1), and $|E(G_{0})|=\frac{ex_{k}}{2}$. Take $F=E(G_{0})\cup E_{V(G_{0})}$ which is required.

A k-component edge cut F of $\mathrm{LTQ}_{n}$ is called $c\lambda _{k}$-cut if $|F|=c\lambda _{k}(\mathrm{LTQ}_{n})$.

Lemma 3.6

$c\lambda _{k+1}(\mathrm{LTQ}_{n})\geqslant nk-\frac{ex_{k}}{2}$ for $k\leqslant 2^{[\frac{n}{2}]}$ and $n\geqslant 7$.

Proof

To show that $c\lambda _{k+1}(\mathrm{LTQ}_{n})\geqslant nk-\frac{ex_{k}}{2}$, it suffices to prove $|F|\geqslant nk-\frac{ex_{k}}{2}$, where F is a $c\lambda _{k+1}$-cut of $\mathrm{LTQ}_{n}$. For convenience sake, we assume that n is even. Let F be a $c\lambda _{k+1}$-cut of $\mathrm{LTQ}_{n}$, then $\mathrm{LTQ}_{n}-F$ has exactly $k+1$ components. We use $C_{1}, C_{2},\cdots ,C_{k+1}$ to denote the above $k+1$ components, and suppose $C_{k+1}$ be the largest one.

Case 1.$|V(C_{k+1})|<2^{n-2}$.

This implies that there exist r components $\{C^{'}_{1}, C^{'}_{2},\cdots ,C^{'}_{r}\}\subseteq \{C_{1}, C_{2},\cdots ,C_{k+1}\}$ such that $2^{n-2}\leqslant \sum _{i=1}^{r}|V(C^{'}_{i})|<2^{n-1}$. Let $G^{'}=\mathrm{LTQ}_{n}[\cup _{i=1}^{r}V(C^{'}_{i})]$ and $|V(G^{'})|=m=\sum _{i=0}^{s}2^{t_{i}}$. Obviously, $E_{V(G^{'})}\subseteq F$. From Lemma 3.3, we know that $|E_{V(G^{'})}|\geqslant nm-ex_{m}$ and $nk-\frac{ex_{k}}{2}=\xi (k)\leqslant \xi (2^{\frac{n}{2}})=n2^{\frac{n}{2}}-\frac{ex_{2^{\frac{n}{2}}}}{2}=\frac{3n}{4}\cdot 2^{\frac{n}{2}}$. Next, we show that $nm-ex_{m}\geqslant \frac{3n}{4}\cdot 2^{\frac{n}{2}}$. Let $m^{'}=m-2^{t_{0}}$, then $m^{'}<2^{n-2}$. By the observation, it is easy to get the following:

$$\begin{aligned} nm-ex_{m}&=n2^{t_{0}}+n(2^{t_{1}}+\cdots +2^{t_{s}})-t_{0}2^{t_{0}}-\left( \sum _{i=1}^{s}t^{i}2^{t_{i}}+\sum _{i=1}^{s}2\cdot i\cdot 2^{t_{i}}\right) \\&=(n-t_{0})2^{t_{0}}+\left( n\sum _{i=1}^{s}2^{t_{i}}-\left( \sum _{i=1}^{s}t_{i}2^{t_{i}}+\sum _{i=1}^{s}2\cdot i\cdot 2^{t_{i}}\right) \right) \\&=(n-t_{0})2^{t_{0}}+nm^{'}-ex_{m^{'}}-2m^{'}\\&\geqslant (n-t_{0})2^{t_{0}}\\&=(n-t_{0})\cdot 2^{t_{0}-\frac{n}{2}}\cdot 2^{\frac{n}{2}}. \end{aligned}$$

Since $t_{0}=n-2$, we have $(n-t_{0})\cdot 2^{t_{0}-\frac{n}{2}}\geqslant \frac{3n}{4}$ for $n\geqslant 7$. Thus, $|F|\geqslant |E_{V(G^{'})}|\geqslant \frac{3n}{4}\cdot 2^{\frac{n}{2}}\geqslant nk-\frac{ex_{k}}{2}$ when $|V(C_{k+1})|<2^{n-2}$.

Case 2.$|V(C_{k+1})|\geqslant 2^{n-2}$.

Denote $|V(C_{i})|=q_{i}$ and $\sum _{i=1}^{k}q_{i}=q$. The case $q\geqslant 2^{n-2}$ can be proved by a similar discussion as Case 1. So we assume $q<2^{n-2}$.

Case 2.1.$q=k$.

This implies that $|V(C_{i})|=q_{i}=1$ for $1\leqslant i\leqslant k$. Then, $|F|\geqslant nk-\frac{ex_{k}}{2}$ by Lemmas 2.3 and 3.3.

Case 2.2.$q>k$.

Let $G^{*}=\mathrm{LTQ}_{n}[\cup _{i=1}^{k}V(C_{i})]$ and $F^{'}=F\cap E(G^{*})$. Obviously, $E_{V(C_{i})}\subseteq F$ ($1\leqslant i\leqslant k$). Then, $|F|\geqslant |\cup _{i=1}^{k}E_{V(C_{i})}|=|E_{V(C_{1})}|+|E_{V(C_{2})}|+\cdots +|E_{V(C_{k})}|-|F^{'}|$. Note that $|E_{V(C_{i})}|=nq_{i}-2|E(C_{i})|$, $|F^{'}|\leqslant \frac{ex_{q}}{2}-|\cup _{i=1}^{k}E(C_{i})|$ and $E(C_{i})\cap E(C_{j})=\varnothing$ for $1\leqslant i\ne j\leqslant k$. By Lemma 3.4, we can obtain

$$\begin{aligned} |F|\geqslant |\cup _{i=1}^{k}E_{V(C_{i})}|&=|E_{V(C_{1})}|+|E_{V(C_{2})}|+\cdots +|E_{V(C_{k})}|-|F^{'}| \\&\geqslant \sum _{i=1}^{k}(nq_{i}-2|E(C_{i})|)-\left( \frac{ex_{q}}{2}-|\cup _{i=1}^{k}E(C_{i})|\right) \\&=nq-2\sum _{i=1}^{k}|E(C_{i})|-\frac{ex_{q}}{2}+\sum _{i=1}^{k}|E(C_{i})| \\&=nq-\frac{ex_{q}}{2}-\sum _{i=1}^{k}|E(C_{i})| \\&\geqslant nq-\frac{ex_{q}}{2}-\sum _{i=1}^{k}\frac{ex_{q_{i}}}{2} \\&\geqslant nq-\frac{ex_{q}}{2}-\frac{ex_{q-k+1}}{2}. \end{aligned}$$

Next, we show that $nq-\frac{ex_{q}}{2}-\frac{ex_{q-k+1}}{2}\geqslant nk-\frac{ex_{k}}{2}$.

Let $S=\{v_{1}, v_{2},\cdots ,v_{q}\}\subseteq V(\mathrm{LTQ}_{n})$. By Definition 2.1 and Lemma 2.3, we may pick a subgraph $G_{0}=\mathrm{LTQ}_{n}[S]$ in $\mathrm{LTQ}_{n-1}$, where $G_{0}$ is the subgraph of $\mathrm{LTQ}_{n}$ in (2.1). Then, $|E(G_{0})|=\frac{ex_{q}}{2}$. Since $q-k+1<q$, we can pick a subgraph $G_{1}\subseteq G_{0}$ such that $|V(G_{1})|=q-k+1$ and $|E(G_{1})|=\frac{ex_{q-k+1}}{2}$ (here we pick the subgraph $G_{1}$ that has the same structural property as $G_{0}$ in (2.1)).

Claim. There exists a node $u\in V(G_{1})$ such that $d_{G_{1}}(u)=s+1$, where $q-k=\sum _{i=0}^{s}2^{t_{i}}$.

If $q-k$ is even, then $|V(G_{1})|=q-k+1=2^{t_{0}}+\cdots +2^{t_{s}}+2^{t_{s+1}}$ and $t_{s+1}=0$. From (2.1), we know that $G_{1}=\mathrm{LTQ}_{n}[V(\mathrm{LTQ}^{0})\cup \cdots \cup V(\mathrm{LTQ}^{s})\cup V(\mathrm{LTQ}^{s+1})]$ and $\mathrm{LTQ}^{s+1}$ is isomorphic to $K_{1}$. Let $V(\mathrm{LTQ}^{s+1})=\{u_{1}\}$. Clearly, $|N_{G_{1}}(u_{1})\cap V(\mathrm{LTQ}^{j})|=1$ for $0\leqslant j\leqslant s$. Thus, $d_{G_{1}}(u_{1})=s+1$.

If $q-k$ is odd, then $q-k=2^{t_{0}}+\cdots +2^{t_{s}}$ and $t_{s}=0$. This implies that $|V(G_{1})|=q-k+1=2^{t_{0}}+\cdots +2^{t_{s}}$ and $t_{s}=1$. Similarly, we have $G_{1}=\mathrm{LTQ}_{n}[V(\mathrm{LTQ}^{0})\cup \cdots \cup V(\mathrm{LTQ}^{s})]$ and $\mathrm{LTQ}^{s}$ is isomorphic to $K_{2}$ by (2.1). Let $V(\mathrm{LTQ}^{s})=\{u_{1}, u_{2}\}$, then $|N_{G_{1}}(u_{i})\cap V(\mathrm{LTQ}^{j})|=1$ for $i=1, 2$ and $0\leqslant j\leqslant s$. Thus, $d_{G_{1}}(u_{i})=s+1$ for $i=1, 2$.

Fig. 2

The edges between the components

Label the nodes of $G_{0}$ by $v_{1}, v_{2},\cdots ,v_{q}$ and the nodes of $G_{1}$ by $v_{q}, v_{q-1},\cdots ,v_{k+1}, v_{k}$ such that $d_{G_{1}}(v_{k})=s+1$. Let $k<q$, $X=\{v_{1}, v_{2},\cdots ,v_{k}\}$, $X^{'}=\{v_{1}, v_{2},\cdots ,v_{k-1}\}$ and $|E(\mathrm{LTQ}_{n}[X^{'}])|=f_{0}$. Clearly, $|\cup _{i=1}^{k}E_{v_{i}}|=nk-|E(\mathrm{LTQ}_{n}[X])|\geqslant nk-\frac{ex_{k}}{2}$. Thus, by Fig. 2, we can get

$$\begin{aligned} \begin{aligned} f_{0}+f_{1}+f_{2}+f_{3}+f_{4}+f_{5}&=nq-2|E(G_{0})|+(|E(G_{0})|-|E(G_{1})|) \\&=nq-\frac{ex_{q}}{2}-\frac{ex_{q-k+1}}{2}\\ \end{aligned} \end{aligned}$$

(3.1)

and

$$\begin{aligned} f_{0}+f_{1}+f_{2}+f_{3}+f_{4}+f_{6}=|\cup _{i=1}^{k}E_{v_{i}}|\geqslant nk-\frac{ex_{k}}{2}. \end{aligned}$$

(3.2)

From (3.1) and (3.2), we know that the inequality $nq-\frac{ex_{q}}{2}-\frac{ex_{q-k+1}}{2}\geqslant nk-\frac{ex_{k}}{2}$ is equivalent to $f_{5}\geqslant f_{6}$. Note that $G_{0}\subseteq \mathrm{LTQ}_{n-1}$ and $q-k=\sum _{i=0}^{s}2^{t_{i}}$, then $f_{5}\geqslant q-k\geqslant s+1=d_{G_{1}}(v_{k})=f_{6}$.

When n is odd, the argument is similar. We omit it.

Combining Lemmas 3.5 and 3.6, we obtain the following main result immediately.

Theorem 3.7

$c\lambda _{k+1}(\mathrm{LTQ}_{n})=nk-\frac{ex_{k}}{2}$ for $k\leqslant 2^{[\frac{n}{2}]}$ and $n\geqslant 7$. Moreover, for any $c\lambda _{k+1}$-cut F of $\mathrm{LTQ}_{n}$, $\mathrm{LTQ}_{n}-F$ has one large component plus k singletons.

Setting $k=2=2^{1}$ and $k=3=2^{1}+2^{0}$ in Theorem 3.7, respectively, we obtain Theorem 3.1 for $n\geqslant 7$.