The generalized 4-connectivity of locally twisted cubes

Abstract

The hypercube is one of the most famous interconnection networks as the topology structure for parallel and distributed systems because of its many good properties. The locally twisted cube, an important variant of hypercube, has lower diameter compared with the same dimensional hypercube, and thus attracts much interesting of many researchers. For $L \subseteq V(G)$, the L-tree means a tree joining each node of L. The L-trees $T_1, T_2, \ldots , T_{l}$ are internally disjoint if $V(T_a) \cap V(T_b)=L$ and $E(T_a) \cap E(T_b)=\emptyset$ for any two different integers $a, b \in \{1, 2, \ldots , l\}$. Let $\kappa (L)=\max \{l \mid T_1, T_2, \ldots , T_l$ are internally disjoint L-trees $\}$ and $\kappa _l(G)=$min$\{\kappa (L) \mid L \subseteq V(G)$ and $\vert L \vert =l\}$. For a graph G, the generalized l-connectivity, denoted by $\kappa _l(G)$, is an extension of connectivity to better evaluate the fault-tolerance of networks. For the n-dimensional locally twisted cube, in this paper, we show that $\kappa _4(LTQ_n)=n-1$, where $n \ge 2$. Since $\kappa _4(LTQ_n) \le \delta (LTQ_n)-1$ and $LTQ_n$ is n-regular, our result is optimal.

1 Introduction

Parallel and distributed systems use an interconnection network as a topological structure to connect hundreds and thousands of processors, so the interconnection network is an important factor affecting the system performance [1,2,3]. An interconnection network is represented by a simple graph, in which the processors and the communication links are represented by the nodes and edges respectively. The hypercube as one of the best known interconnection network has quite good properties including recursive structure, high symmetry, regularity, low degree, which are crucial for designing massively parallel or distributed systems [2]. However, the hypercube has large diameter among the hypercube-like cubes [4]. And hypercube is a bipartite graph, when design the parallel algorithm, all the processors cannot make best use. To remedy these defects, many other hypercube-like cubes were proposed, one of them is locally twisted cube [5]. The locally twisted cube as one of the important variants of hypercube has the same regularity, connectivity, and the number of nodes as the same dimensional hypercube [5]. But for the same dimension n, the locally twisted cube $LTQ_n$ has other properties superior to the hypercube $Q_n$. For example, the diameter of $LTQ_n$ is $\lceil \frac{n+3}{2}\rceil$ when $n \ge 5$, which is about half of $Q_n$ [5]. The $LTQ_n$ is not bipartite, so it contains both odd and even paths and cycles [6,7,8]. Various properties of the locally twisted cube have been extensively studied [5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25].

As the increasing of the network size, the processors and communication links will inevitable occur failure, which will produce an effect on the reliability and efficiency of the corresponding multiprocessor system. Evaluate the fault tolerance of the network is an important aspect to improve the reliability and efficiency of the corresponding system. Fault tolerance implies that the system will work properly even if some processors of communication links occur failures. Connectivity is a common method to measure the fault tolerance of an interconnection network. In a graph G, the connectivity is $\kappa (G)$ and defined by $\kappa (G)=$min$\{\vert U \vert \mid U \subset V(G)$ and $G-U$ is disconnected or trivial$\}$. G is l-connected if $\kappa (G) \le l$. The classical connectivity makes the assumption that all the neighbors of some vertices are faulty at the same time. But the probability of this case is very small. The generalized connectivity [26] is one of the improvements of classical connectivity to overcome this shortcoming. For $L \subseteq V(G)$, the L-tree means a tree joining each node of L [27]. The L-trees $T_1, T_2, \ldots , T_{l}$ are internally disjoint if $V(T_a) \cap V(T_b)=L$ and $E(T_a) \cap E(T_b)=\emptyset$ for any two different integers $a, b \in \{1, 2, \ldots , l\}$ [27]. Let $\kappa (L)=$max$\vert \{$internally disjoint L-trees$\} \vert$ and $\kappa _l(G)=$min$\{\kappa (L) \mid L \subseteq V(G)$ and $\vert L \vert =l\}$ [27, 28]. Note that when $\vert L \vert =2$, $\kappa _2(G)=\kappa (G)$ [29]. The generalized connectivity provides a more better method to make judgement on the fault tolerance of interconnection networks.

For a given integer l, it is NP-complete to compute the exact value of $\kappa _l(G)$ [30]. In recent years, there are many applications of generalized connectivity, such as $\kappa _3(G)$ when G is a Cartesian product graph [31], the Mycielskian of a graph [32], balanced hypercube [33], augmented cube [34], star graph [35], bubble-sort graph [35], the line graph and total graph for the complete bipartite graph [36], alternating group graph [37], k-ary n-cube [37], split-star network [37], bubble-sort-star graph [37, 38], alternating group graph [39], (n, k)-star graph [39], graph product [40], locally twisted cube [41], and the generalized hypercube [41], and $\kappa _4(G)$ when G is of hypercube [27], exchanged hypercube [28], hierarchical cubic network [42], dual cube [43], and (n, k)-star network [44]. For $LTQ_n$ ($n \ge 2)$, it has been determined that $\kappa _3(LTQ_n)=n-1$ [41]. In this paper, we further obtain $\kappa _4(LTQ_n)=n-1$. Since the $LTQ_n$ is n-regular [5] and $\kappa _4(LTQ_n) \le \delta (LTQ_n)-1$, this result is optimal.

This paper contains four sections. In the next section, the necessary terminologies and definitions are introduced. Our main results and conclusion are in Sects. 3 and 4 respectively.

2 Perliminaries

Graph G consists of node set and edge set, which are denoted by V(G) and E(G) respectively. For any edge $e=(x, y)$, x is y’s neighbor, and vice versa, x and y are called adjacent to each other. x (respectively, y) and e are called incident with each other. Denote the degree of u by $d_G(u)=\{(u, v) \mid v \in V(G)\}$ and $\delta (G)=$min$\{d_G(u) \mid u\in V(G)\}$. Let $P[x, y]=\langle x, x_1, x_2, \ldots , x_{k-1}, y \rangle$ be a path that joins x and y, where every two successive nodes are adjacent and x and y are called its two end nodes. Let $\vert V(P)-1 \vert$ be the length of P. If $\vert V(P)-1 \vert =l$, then P is l-path. If $x=y$ and the length is at least three, then the path becomes a cycle. Two paths P[a, b] and Q[a, b] are internally disjoint when $V(P[a, b]) \cap V(Q[a, b])=\{a, b\}$. For two node sets $S=\{s_1, s_2, \ldots , s_l\}$ and $T=\{t_1, t_2, \ldots , t_l\}$ in V(G), the (S, T)-paths denote node disjoint paths $P_i$s, where $P_i$ joins $s_i$ and $t_i$ for $1 \le i \le l$. Furthermore, if $S=\{s\}$, then (S, T)-paths become (s, T)-paths which is a l-fan.

The following are two definitions of $LTQ_n$. Throughout this paper, we use ‘$\oplus$’ to denote modulo 2 addition.

Definition 1

([24]) $LTQ_n$ has the following recursive definition.

(1) $LTQ_2=\langle 10, 11, 01, 00, 10 \rangle$, which is a 4-cycle.

(2) For $n \ge 3$, $LTQ_n$ consists of $L^{0}$ and $R^{1}$, where $L^0 \cong R^1 \cong LTQ_{n-1}$ and the foremost label of each node of $L^0$ (respectively, $R^1$) is 0 (respectively, 1). Each node $0u_2u_3 \ldots u_n \in V(L^0)$ is adjacent to $1(u_2 \oplus u_n)u_3 \ldots u_n \in V(R^1)$.

By Definition 1, let $LTQ_n=L^0 \otimes R^1$. Since $LTQ_{n-1}$ is also recursively defined, we can further denote $L^0=L^{00} \otimes L^{01}$ and $R^{1}=R^{10} \otimes R^{11}$, where each node of $L^{0j}$ and $R^{1j}$ with the foremost two labels are 0j and 1j respectively, where $j \in \{0, 1\}$. Hence, $LTQ_n=(L^{00} \otimes L^{01}) \otimes (R^{10} \otimes R^{11})$. For any node x in $L^0$ (respectively, $R^1$), its only one neighbor in $R^1$ (respectively, $L^0$) is denoted by $x''$. For any node $y \in V(L^{0i})$ (respectively, $R^{1i}$), there is also only one neighbor, denoted by $y'$, in $L^{0j}$ (respectively, $R^{1j}$), where $i=0$ or 1 and $j=1-i$. The edge $(x, x'')$ (respectively, $(y, y')$) is called the crossing edge between $L^0$ and $R^1$ (respectively, $L^{0i}$ and $L^{0j}$ (respectively, $R^{1i}$ and $R^{1j}$)). Furthermore, x and $x''$ (respectively, y and $y'$) are called each other’s crossing neighbors. For $x_i \in \{0, 1\}$, we denote $\overline{x}_i=1-x_i$. The $LTQ_2$ and $LTQ_3$ are depicted in Fig. 1.

Fig. 1

(a) $LTQ_2$; (b) $LTQ_3$; (c) $LTQ_3$

$LTQ_n$ has the following equivalent definition.

Definition 2

([24]) $LTQ_n=(V(LTQ_n), E(LTQ_n))$, where $V(LTQ_n)=\{u_1u_2 \ldots u_i \ldots u_{n-1}u_n \mid u_i \in \{0, 1\}, 1 \le i \le n\}$, and $n \ge 2$. The node $u=u_1u_2 \ldots u_n$ is adjacent to $v=v_1v_2 \ldots v_n$ if and only if one of the following conditions holds:

(1) for some i, $u_i=\overline{v}_i$ and $u_{i+1}=v_{i+1} \oplus v_n$, and for $j \notin \{i, i+1\}$, $x_j=y_j$, where $1 \le i, j \le n-2$ and $n \ge 3$;

(2) for $i \in \{n-1, n\}$, $u_i=\overline{v}_i$, where $n \ge 2$, and for $j \ne i$, $u_j=v_j$.

Lemma 1

([41]) $\kappa _3(LTQ_n)=n-1$, where $n \ge 2$.

The following lemma is used to find the upper bound of $k_4(LTQ_n)$.

Lemma 2

([45]) If G contains an edge (x, y) satisfying $d_G(x)=d_G(y)=\delta (G)$, then $\kappa _l(G) \le \delta (G)-1$, where $3 \le l \le \vert V(G)\vert$.

The following three famous lemmas are powerful tools to find internally disjoint paths between two vertices, a vertex and a set, and two vertex sets, respectively.

Lemma 3

([46]) For a l-connected graph G, and two different nodes a and b, G possesses l internally disjoint paths joining a and b.

Lemma 4

([46]) For a l-connected graph G, $a \in V(G)$, and $U \subseteq V(G)-\{a\}$ with $\vert U \vert \ge l$, G contains (a, U)-paths.

Lemma 5

([46]) For a l-connected graph G, and two node sets W, Z with $\vert W \vert \ge l$, $\vert Z \vert \ge l$ and $W \cap Z=\emptyset$, G contains l pairwise (W, Z)-paths.

3 Main results

In this section, we will prove our main result. We will firstly find $n-1$ internally disjoint L-trees in the n-dimensional locally twisted cube $LTQ_n$ according to the distributions of the vertices in $L \subset V(LTQ_n)$ with $\vert L \vert =4$. Before doing that, we will prove the following three lemmas that are used to prove the main result.

Lemma 6

Let $LTQ_n=(L^{00} \otimes L^{01}) \otimes (R^{10} \otimes R^{11})$ ($n \ge 3$). For any node $x \in V(L^{0i})$ (respectively, $y \in V(R^{1i})$), its crossing neighbor $x'' \in V(R^1)$ (respectively, $y'' \in V(L^0)$) is in $R^{1i}$ or $R^{1j}$ (respectively, $L^{0i}$ or $L^{0j}$), where $i=0$ or 1 and $j=1-i$.

Proof

By symmetry of $L^0$ and $R^1$, $L^{00}$ and $L^{01}$, and $R^{10}$ and $R^{11}$, we only consider $x \in V(L^{00})$. The cases of $x \in V(L^{01})$, $y \in V(R^{10})$, $y \in V(R^{11})$ can be proved similarly.

For $n=3$, $x=000 \in V(L^{00})$ or $x=001 \in V(L^{00})$. If $x=000$, then $x''=100 \in V(R^{10})$. If $x=001$, then $x''=111 \in V(R^{11})$.

For $n \ge 4$, we denote $x=00x_3 \ldots x_{n-1}x_n \in V(L^{00})$. If $x_n=0$, then $x''=10x_3 \ldots x_{n-1}0 \in V(R^{10})$. If $x_n=1$, then $x''=11x_3 \ldots x_{n-1}1 \in V(R^{11})$.

So the lemma holds.

$\square$

Lemma 7

Let $LTQ_n=(L^{00} \otimes L^{01}) \otimes (R^{10} \otimes R^{11})$ ($n \ge 4$). For any node $u \in V(L^{0j})$ (respectively, $u \in V(R^{1j})$), if $u'' \in V(R^{1j})$ (respectively, $u'' \in V(L^{0j})$), then u has $n-3$ neighbors $u_i$s ($3 \le i \le n-1$) in $L^0$ (respectively, $R^1$) such that $u_i''$ in $V(R^{1j})$ (respectively, $V(L^{0j})$), and two neighbors $u_2$ and $u_{n}$ in $L^0$ (respectively, $R^1$) such that $u_2'', u_{n}''$ in $V(R^{1k})$ (respectively, $V(L^{0k})$), where $j=0$ or 1 and $k=1-j$; if $u'' \in V(R^{1k})$ (respectively, $u'' \in V(L^{0k})$), then u has $n-3$ neighbors $u_i$s ($3 \le i \le n-1$) in $L^0$ (respectively, $R^1$) such that $u_i''$ in $V(R^{1k})$ (respectively, $V(L^{0k})$), and two neighbors $u_2$ and $u_{n}$ in $L^0$ (respectively, $R^1$) such that $u_2'', u_{n}''$ in $V(R^{1j})$ (respectively, $V(L^{0j})$), where $j=0$ or 1 and $k=1-j$,

Proof

By symmetry of $L^0$ and $R^1$, $L^{00}$ and $L^{01}$, and $R^{10}$ and $R^{11}$, we only consider $u \in V(L^{00})$. The cases of $u \in V(L^{01})$, $u \in V(R^{10})$ and $u \in V(R^{11})$ can be proved similarly. Let $u=00x_3 \ldots x_{n-1}x_n \in V(L^{00})$.

If $x_n=0$, then $u''=10x_3 \ldots x_{n-1}0 \in V(R^{10})$. By Definition 2, $u_2=01x_3 \ldots x_{n-1}0$, $u_i=00 \ldots \overline{x}_ix_{i+1} \ldots x_{n-1}0$ for $3 \le i \le n-2$, $u_{n-1}=00x_3 \ldots \overline{x}_{n-1}0$ and $u_{n}=00x_3 \ldots x_{n-1}1$. Hence, $u_2''=11x_3 \ldots x_{n-1}0 \in V(R^{11})$, $u_i''=10 \ldots \overline{x}_ix_{i+1} \ldots x_{n-1}0 \in V(R^{10})$ for $3 \le i \le n-2$, $u_{n-1}''=10x_3 \ldots \overline{x}_{n-1}0 \in V(R^{10})$ and $u_n''=11x_3 \ldots x_{n-1}1 \in V(R^{11})$.

If $x_n=1$, then $u''=11x_3 \ldots x_{n-1}1 \in V(R^{11})$. By Definition 2, $u_2=01\overline{x}_3 \ldots x_{n-1}1$, $u_i=00 \ldots \overline{x}_i\overline{x}_{i+1} \ldots 1$ for $3 \le i \le n-2$, $u_{n-1}=00x_3 \ldots \overline{x}_{n-1}1$, $u_n=00x_3 \ldots x_{n-1}0$. Then $u_2''=10\overline{x}_3 \ldots x_{n-1}1 \in V(R^{10})$, $u_i''=11 \ldots \overline{x}_i\overline{x}_{i+1} \ldots 1 \in V(R^{11})$ for $3 \le i \le n-2$, $u_{n-1}''=11x_3 \ldots \overline{x}_{n-1}1 \in V(R^{11})$ and $u_n''=10x_3 \ldots x_{n-1}0 \in V(R^{10})$.

So the lemma holds.

$\square$

Lemma 8

Let $LTQ_n=(L^{00} \otimes L^{01}) \otimes (R^{10} \otimes R^{11})$ ($n \ge 3$). There exist $2^{n-3}$ 4-cycles like $\langle a, b, b'', a'', a \rangle$, where $a \in V(L^{00})$, $b \in V(L^{01})$, $a'' \in V(R^{10})$, and $b'' \in V(R^{11})$, and there exist $2^{n-3}$ 4-cycles like $\langle c, d, d'', c'', c \rangle$, where $c \in V(L^{00})$, $d \in V(L^{01})$, $c'' \in V(R^{11})$ and $d'' \in V(R^{10})$.

Proof

For $n=3$, let $\langle a, b, b'', a'', a \rangle =\langle 000, 010, 110, 100, 000 \rangle$ and $\langle c, d, d'', c'',c \rangle =\langle 001, 011, 101, 111, 001 \rangle$ in $LTQ_3$. In the following, we consider $n \ge 4$.

Denote $a=00a_3a_4 \ldots a_{n-1}0 \in V(L^{00})$, where $a_i=0$ or 1 for $i \in \{3, 4,\ldots , n-1\}$. Let $b=01a_3a_4 \ldots a_{n-1}0 \in V(L^{01})$. Then $a''=10a_3a_4 \ldots a_{n-1}0 \in V(R^{10})$ and $b''=11a_3a_4 \ldots a_{n-1}0 \in V(R^{11})$. So $\langle a, b, b'', a'', a \rangle$ is a 4-cycle. Note that there exist $2^{n-3}$ nodes like a, so there are $2^{n-3}$ such 4-cycles.

Denote $c=00c_3c_4 \ldots c_{n-1}1 \in V(L^{00})$, where $c_i=0$ or 1 for $i \in \{3, 4, \ldots , n-1\}$. Let $d=01\overline{c}_3c_4 \ldots c_{n-1}1 \in V(L^{01})$. Then $c''=11c_3c_4 \ldots c_{n-1}1 \in V(R^{11})$ and $d''=10\overline{c}_3c_4 \ldots c_{n-1}1 \in V(R^{10})$. Hence $\langle c, d, d'', c'', c \rangle$ is a 4-cycle. Note that there exist $2^{n-3}$ nodes like c, so there exist $2^{n-3}$ such 4-cycles. So the lemma holds. $\square$

The following two lemmas are the basic cases of the main result when $n=2$ and $n=3$, respectively.

Lemma 9

$\kappa _4(LTQ_2)=1$.

Proof

Since $LTQ_2$ is 2-regular, by Lemma 2, $\kappa _4(LTQ_2) \le 1$. Since $LTQ_2$ is a 4-cycle with four nodes, there exists a 3-path joining these four nodes. So the lemma holds. $\square$

Lemma 10

$\kappa _4(LTQ_3)=2$.

Proof

Since $LTQ_3$ is 3-regular, by Lemma 2, $\kappa _4(LTQ_3) \le 2$. For any node set L with $\vert L\vert =4$, in the following, we will show that $LTQ_3$ contains two internally disjoint L-trees. Note from Fig. 1b, c that the outside 4-cycle $C_1=\langle 010, 110, 100, 000, 010 \rangle$ is symmetric to the inside 4-cycle $C_2=\langle 011, 101, 111, 001, 011 \rangle$. By Fig. 1b, one can see that $LTQ_3$ is up and down symmetric by the centerline of the edge (010, 000) and is left-right symmetric by the centerline of the edge (010, 110). Denote $L=\{a, b, c, d\}$. We only need to consider three cases, that is (i) four nodes of L are in $C_1$; (ii) three nodes of L are in $C_1$, the other one node of L in $C_2$; (iii) two nodes of L are in $C_1$ and another two nodes of L are in $C_2$. For case (i), suppose that $a=010, b=110, c=100, d=000$. Let $P_1=\langle 110, 010, 000, 100 \rangle$ and $P_2=\langle 010, 011, 101, 100, 110, 111, 001, 000 \rangle$. Then $P_1$ and $P_2$ are two desired L-trees. For cases (ii) and (iii), by the symmetry of $LTQ_3$, we only need to take into account the distributions of a, b, c, d as shown in Fig. 2. $LTQ_3$ contains two desired L-trees which are colored red and green respectively in Fig. 2. So the lemma holds.

Fig. 2

(1)–(4) for case (ii) and (5)–(12) for case (iii) in the proof of Lemma 10

$\square$

In the following, we will firstly find $n-1$ internally disjoint L-trees in $LTQ_n$ according to the distributions of the vertices in L.

Lemma 11

Let $LTQ_n=L^0 \otimes R^1=(L^{00} \otimes L^{01}) \otimes (R^{10} \otimes R^{11})$ ($n \ge 4$). Let $L \subset V(LTQ_n)$ with $\vert L \cap V(L^0) \vert =3$ and $\vert L \cap V(R^1) \vert =1$. Then $LTQ_n$ contains $n-1$ internally disjoint L-trees.

Proof

Without loss of generality, let $L \cap V(L^0)=\{a, b, c\}$ and $L \cap V(R^1)=\{d\}$. By the symmetry of $R^{10}$ and $R^{11}$, we only need to consider that $d \in V(R^{10})$. By Lemma 1, $L^0$ contains $n-2$ internally disjoint L-trees, denoted by $T_1', T_2', \ldots , T_{n-2}'$, joining a, b, c. We pick one node, denoted by $u_1, \ldots , u_{n-2}$, in $T_1', \ldots , T_{n-2}'$ respectively, such that $u_1'', \ldots , u_{n-2}''$ are in $R^{10}$. (If some $u_i'' \notin V(R^{10})$, by Lemma 7, there exists a neighbor, denoted by $v_i$, of $u_i$ in $V(L^{0})$ such that $v_i'' \in V(R^{10})$. We use $\langle u_i, v_i, v_i'' \rangle$ to instead of $(u_i, u_i'')$.) Let $U''=\{u_1'', \ldots , u_{n-2}''\}$. Since $R^{10}$ is $(n-2)$-connected, by Lemma 4, there exist $(d, U'')$-paths, denoted by $P_i$s, such that $P_i$ joins d and $u_i''$ in $R^{10}$, where $1 \le i \le n-2$. Let $T_i=T_i' \cup (u_i, u_i'') \cup P_i$, where $1 \le i \le n-2$. By Definition 1, $(d, d') \in V(LTQ_n)$ and $d' \in V(R^{11})$. We further consider the following cases to construct the $T_{n-1}$.

Case 1. $\{a'', b'', c''\} \cap \{d\}=\emptyset$.

Case 1.1. $\vert \{a'', b'', c''\} \cap V(R^{10}) \vert =0$.

By Lemma 6, $\vert \{a'', b'', c''\} \cap V(R^{11}) \vert =3$. Since $R^{11}$ is $(n-2)$-connected, there exists a tree $T_{n-1}'$ joining $d'$ and $a'', b'', c''$. Let $T_{n-1}=T_{n-1}' \cup (a, a'') \cup (b, b'') \cup (c, c'') \cup (d, d')$ (See Fig. 3a).

Fig. 3

(a) $\vert \{a'', b'', c''\} \cap V(R^{10}) \vert =0$; (b) $\vert \{a'', b'', c''\} \cap V(R^{10}) \vert =1$

• Case 1.2. $\vert \{a'', b'', c''\} \cap V(R^{10}) \vert \ge 1$.

If $\vert \{a'', b'', c''\} \cap V(R^{10}) \vert =1$. Without loss of generality, let $a'' \in V(R^{10})$. Then $b''$ and $c''$ are in $R^{11}$. By Definition 1, $a''$ has a crossing neighbor, denoted by $a^*$, in $V(R^{11})$. Since $R^{11}$ is $(n-2)$-connected, there exists a tree $T_{n-1}'$ joining $d'$ and $a^*, b'', c''$. Let $T_{n-1}=T_{n-1}' \cup (a, a'') \cup (a'', a^*) \cup (b, b'') \cup (c, c'') \cup (d, d')$ (See Fig. 3b).

If $\vert \{a'', b'', c''\} \cap V(R^{10}) \vert =2$. Without loss of generality, let $a'', b'' \in V(R^{10})$. Then $c''$ is in $R^{11}$. By Definition 1, $a''$ (respectively, $b''$) has a crossing neighbor, denoted by $a^*$ (respectively, $b^*$) in $R^{11}$. Since $R^{11}$ is $(n-2)$-connected, there exists a tree $T_{n-1}'$ joining $d'$ and $a^*, b^*, c''$. Let $T_{n-1}=T_{n-1}' \cup (a, a'') \cup (a'', a^*) \cup (b, b'') \cup (b'', b^*) \cup (c, c'') \cup (d, d')$.

If $\vert \{a'', b'', c''\} \cap V(R^{10}) \vert =3$. By Definition 1, $a''$ (respectively, $b''$, $c''$) has a crossing neighbor, denoted by $a^*$ (respectively, $b^*$, $c^*$) in $R^{11}$. Since $R^{11}$ is $(n-2)$-connected, there exists a tree $T_{n-1}'$ joining $d'$ and $a^*, b^*, c^*$. Let $T_{n-1}=T_{n-1}' \cup (a, a'') \cup (a'', a^*) \cup (b, b'') \cup (b'', b^*) \cup (c, c'') \cup (c'', c^*) \cup (d, d')$.

• Case 2. $\{a'', b'', c''\} \cap \{d\} \ne \emptyset$.

By Definition 1, there exists only one node of $\{a'', b'', c''\}$ may equal to d. Without loss of generality, let $a''=d$.

• Case 2.1. $\vert \{b'', c''\} \cap V(R^{10}) \vert =0$.

In this case, $b''$ and $c''$ are in $V(R^{11})$. Since $R^{11}$ is $(n-2)$-connected, there exists a tree $T_{n-1}'$ joining $d'$ and $b'', c''$. Let $T_{n-1}=T_{n-1}' \cup (a, d) \cup (d, d') \cup (b, b'') \cup (c, c'')$ (See Fig. 4a).

Fig. 4

(a) $\vert \{b'', c''\} \cap V(R^{10}) \vert =0$; (b) $\vert \{b'', c''\} \cap V(R^{10}) \vert =1$

Case 2.2. $\vert \{b'', c''\} \cap V(R^{10}) \vert \ge 1$.

If $\vert \{b'', c''\} \cap V(R^{10}) \vert =1$. Without loss of generality, let $b'' \in V(R^{10})$. Then $c'' \in V(R^{11})$. By Definition 1, $b''$ has a crossing neighbor, denoted by $b^*$, in $R^{11}$. Since $R^{11}$ is $(n-2)$-connected, there exists a tree $T_{n-1}'$ joining $d'$ and $b^*, c''$. Let $T_{n-1}=T_{n-1}' \cup (a, d) \cup (d, d') \cup (b, b'') \cup (b'', b^*) \cup (c, c'')$ (See Fig. 4b).

If $\vert \{b'', c''\} \cap V(R^{10}) \vert =2$. By Definition 1, $b''$ (respectively, $c''$) has a crossing neighbor, denoted by $b^*$ (respectively, $c^*$), in $R^{11}$. Since $R^{11}$ is $(n-2)$-connected, there exists a tree $T_{n-1}'$ joining $d'$ and $b^*, c^*$. Let $T_{n-1}=T_{n-1}' \cup (a, d) \cup (d, d') \cup (b, b'') \cup (b'', b^*) \cup (c, c'') \cup (c'', c^*)$.

By the above cases, the $T_i$s ($1 \le i \le n-1$) are $n-1$ desired L-trees.

So the lemma holds.

$\square$

Lemma 12

Let $LTQ_n=L^0 \otimes R^1=(L^{00} \otimes L^{01}) \otimes (R^{10} \otimes R^{11})$ ($n \ge 4$). Let $L \subset V(LTQ_n)$ with $\vert L \cap V(L^0)\vert =\vert L \cap V(R^{10})\vert =2$. Then there exists a L-tree $T_{n-1}$ satisfying $\vert T_{n-1} \cap V(L^0) \vert =2$ and $\vert T_{n-1} \cap V(R^{10})\vert =2$.

Proof

Without loss of generality, let $L \cap V(L^0)=\{a, b\}$ and $L \cap V(R^{10})=\{c, d\}$. By Definition 1, $c', d'$ are in $R^{11}$.

Case 1. $\vert \{a'', b''\} \cap V(R^{10}) \vert =0$.

In this case, $a'', b'' \in V(R^{11})$. Since $R^{11}$ is $(n-2)$-connected, $R^{11}$ contains a tree $T_{n-1}'$ joining $a'', b'', c', d'$. Let $T_{n-1}=T_{n-1}' \cup (a, a'') \cup (b, b'') \cup (c, c') \cup (d, d')$ (See Fig. 5a).

Case 2. $\vert \{a'', b''\} \cap V(R^{10}) \vert =1$.

Without loss of generality, let $a'' \in V(R^{10})$. Then $b'' \in V(R^{11})$. By Definition 1, $a''$ has a crossing neighbor, denoted by $a^*$, in $R^{11}$. Since $R^{11}$ is $(n-2)$-connected, there exists a tree $T_{n-1}'$ joining $a^*, b'', c', d'$ in $R^{11}$. Let $T_{n-1}=T_{n-1}' \cup (a, a'') \cup (a'', a^*) \cup (b, b'') \cup (c, c') \cup (d, d')$.

Case 3. $\vert \{a'', b''\} \cap V(R^{10}) \vert =2$.

By Definition 1, $a''$ (respectively, $b''$) has a crossing neighbor $a^*$ (respectively, $b^*$) in $R^{11}$. Since $R^{11}$ is $(n-2)$-connected, $R^{11}$ contains a tree $T_{n-1}'$ joining $a^*, b^*, c', d'$. Let $T_{n-1}=T_{n-1}' \cup (a, a'') \cup (a'', a^*) \cup (b, b'') \cup (b'', b^*) \cup (c, c') \cup (d, d')$ (See Fig. 5b).

Fig. 5

(a) $\vert \{a'', b''\} \cap V(R^{10}) \vert =0$; (b) $\vert \{a'', b''\} \cap V(R^{10}) \vert =2$

$\square$

Lemma 13

Let $LTQ_n=L^0 \otimes R^1=(L^{00} \otimes L^{01}) \otimes (R^{10} \otimes R^{11})$ ($n \ge 4$). Let $L \subset V(LTQ_n)$ with $\vert L \cap V(L^{00}) \vert =\vert L \cap V(R^{10}) \vert =2$. Then $LTQ_n$ contains $n-1$ internally disjoint L-trees.

Proof

Denote $L \cap V(L^{00})=\{a, b\}$ and $L \cap V(R^{10})=\{c, d\}$. By Lemma 12, $LTQ_n$ contains a L-tree $T_{n-1}$ satisfying $\vert T_{n-1} \cap V(L^0) \vert =2$ and $\vert T_{n-1} \cap R^{10} \vert =2$. In the following, we will construct $T_i$s for $1 \le i \le n-2$.

Since $L^{00}$ (respectively, $R^{10}$) is $(n-2)$-connected, by Lemma 3, $L^{00}$ (respectively, $R^{10}$) contains internally disjoint paths $P_i$s (respectively, $Q_i$s) ($1 \le i \le n-2$) joining a and b (respectively, c and d). In the following, if $(a, b) \in E(L^{00})$ (respectively, $(c, d) \in E(R^{10})$, we let $P_1=(a, b)$ (respectively, $Q_1=(c, d)$).

• Case 1. $\{c'', d''\} \cap V(L^{01}) \ne \emptyset$.

Without loss of generality, let $c'' \in V(L^{01})$. Select nodes, denoted by $u_2, \ldots , u_i, \ldots , u_{n-2}$, in $P_2, \ldots , P_i, \ldots , P_{n-2}$ respectively. By Definition 1, $b', u_2', \ldots , u_i', \ldots , u_{n-2}'$ are in $L^{01}$. Select nodes, denoted by $v_2, \ldots , v_i, \ldots , v_{n-2}$, in $Q_2, \ldots , Q_i, \ldots , Q_{n-2}$ respectively such that $v_2'', \ldots , v_i'', \ldots , v_{n-2}''$ are in $L^{01}$. (If there exists some $v_i'' \in V(L^{00})$, by Lemma 7, $v_i$ has a neighbor, denoted by $t_i$, in $R^{10}$ such that $t_i \notin Q_i$ and $t_i'' \in V(L^{01})$. We use $\langle v_i, t_i, t_i'' \rangle$ to instead of $(v_i, v_i'')$.) Let $U'=\{b', u_2', \ldots , u_{n-2}'\}$ and $V''=\{c'', v_2'', \ldots , v_{n-2}''\}$. By Lemma 5, $L^{01}$ contains $(U', V'')$-paths, denoted by $R_1, R_2, \ldots , R_i, \ldots , R_{n-2}$, such that $R_1$ joins $b'$ and $c''$, $R_i$ joins $u_i'$ and $v_i''$, where $2 \le i \le n-2$. Denote $T_1=P_1 \cup (b, b') \cup R_1 \cup (c'', c) \cup Q_1$, and $T_i=P_i \cup (u_i, u_i') \cup R_i \cup (v_i'', v_i) \cup Q_i$ for $2 \le i \le n-2$ (See Fig. 6a).

• Case 2. $\{d'', c''\} \cap V(L^{01})=\emptyset$.

Then $d'' \in V(L^{00})$. Since $L^{00}$ is $(n-2)$-connected, there exists a path $P_0$ joining a and $d''$. Let v be the first node of $P_0 \cap \bigcup _{i=1}^{n-2}P_i$ if $P_0 \cap \bigcup _{i=1}^{n-2}P_i \ne \emptyset$. Without loss of generality, let $v \in P_{n-2}$. Let P be the subpath joining v and $d''$. Select one node, denoted by $u_i$, in $P_i$ for $2 \le i \le n-3$. By Definition 1, $u_i' \in V(L^{01})$ for $2 \le i \le n-3$. Select one node, denoted by $v_i$, in $Q_i$ such that $v_i'' \in V(L^{01})$, where $2 \le i \le n-2$. (If some $v_i'' \notin V(L^{01})$, by Lemma 7, $v_i$ has a neighbor, denoted by $t_i$, in $R^{10}$ such that $t_i \notin Q_i$ and $t_i'' \in V(L^{01})$. We use $\langle v_i, t_i, t_i'' \rangle$ to instead of $(v_i, v_i'')$.) Let $U'=\{b', u_2', \ldots , u_{n-3}'\}$ and $V''=\{v_{n-2}'', v_2'', \ldots , v_{n-3}''\}$. Note that $L^{01}$ is $(n-2)$-connected, by Lemma 5, $L^{01}$ contains $(U', V'')$-paths, denoted by $R_1, \ldots , R_i, \ldots , R_{n-3}$, where $R_1$ joins $b'$ and $v_{n-2}''$, $R_i$ joins $u_i'$ and $v_i''$ for $2 \le i \le n-3$. Let $T_1=P_{n-2} \cup P \cup (d'', d) \cup Q_1$, $T_i=P_i \cup (u_i, u_i') \cup R_i \cup (v_i'', v_i) \cup Q_i$ for $2 \le i \le n-3$, and $T_{n-2}=P_1 \cup (b, b') \cup R_1 \cup (v_{n-2}'', v_{n-2}) \cup Q_{n-2}$ (See Fig. 6b).

By the above cases, $T_i$s ($1 \le i \le n-1$) are desired L-trees.

Fig. 6

(a) $\{c'', d''\} \cap V(L^{01}) \ne \emptyset$; (b) $\{d'', c''\} \cap V(L^{01})=\emptyset$

$\square$

Lemma 14

Let $LTQ_n=L^0 \otimes R^1=(L^{00} \otimes L^{01}) \otimes (R^{10} \otimes R^{11})$ ($n \ge 4$). Let $L \subset V(LTQ_n)$ with $\vert L \cap V(L^{00}) \vert =\vert L \cap V(L^{01}) \vert =1$ and $\vert L \cap V(R^{10}) \vert =2$. Then $LTQ_n$ contains $n-1$ internally disjoint L-trees.

Proof

Without loss of generality, let $L \cap V(L^{00})=\{a\}$, $L \cap V(L^{01})=\{b\}$, and $L \cap V(R^{10})=\{c, d\}$. By Lemma 12, $LTQ_n$ contains an L-tree $T_{n-1}$ satisfying $\vert T_{n-1} \cap V(L^0) \vert =2$ and $\vert T_{n-1} \cap V(R^{10}) \vert =2$. In the following, we will construct $T_i$s for $1 \le i \le n-2$.

Note that $R^{10}$ is $(n-2)$-connected, by Lemma 3, $R^{10}$ contains $n-2$ internally disjoint paths $P_1, P_2, \ldots , P_{n-2}$ joining c and d. (If $(c, d) \in E(R^{10})$, we let $P_1=(c, d)$.) By Lemma 6, $d''$ (respectively, $c''$) is in $L^{00}$ or $L^{01}$. Without loss of generality, let $c'' \in V(L^{00})$. Select nodes, denoted by $u_2, \ldots , u_{n-2}$, in $P_2, \ldots , P_{n-2}$ respectively.

If $u_2'', \ldots , u_{n-2}''$ are in $L^{00}$, by Definition 1, $c'', u_2'', \ldots , u_{n-2}''$ have a crossing neighbor, denoted by $c^*, u_2^*, \ldots , u_{n-2}^*$ respectively, in $L^{01}$. Let $U''=\{c'', u_2'', \ldots , u_{n-2}''\}$ and $U^*=\{c^*, u_2^*, \ldots , u_{n-2}^*\}$. By Lemma 4, there exist $(a, U'')$-paths, denoted by $Q_1, \ldots , Q_i, \ldots , Q_{n-2}$, in $L^{00}$, and $(b, U^*)$-paths, denoted by $R_1, \ldots , R_i, \ldots , R_{n-2}$, in $L^{01}$, where $Q_1$ joins a and $c''$, $Q_i$ joins a and $u_i''$, $R_1$ joins b and $c^*$, $R_i$ joins b and $u_i^*$, and $2 \le i \le n-2$. Let $T_1=P_1 \cup (c, c'') \cup Q_1 \cup (c'', c^*) \cup R_1$ and $T_i=P_i \cup (u_i, u_i'') \cup Q_i \cup (u_i'', u_i^*) \cup R_i$ for $2 \le i \le n-2$ (See Fig. 7).

If some $u_i$ ($2 \le i \le n-2$) has the crossing neighbor $u_i''$ in $L^{01}$, with the similar discussion above, we only need to exchange $u_i''$ and $u_i^*$.

Hence, $T_i$s ($1 \le i \le n-1$) are $n-1$ desired L-trees.

Fig. 7

The illustration Lemma 14

$\square$

Lemma 15

Let $LTQ_n=L^0 \otimes R^1=(L^{00} \otimes L^{01}) \otimes (R^{10} \otimes R^{11})$ ($n \ge 4$). Let $L \subset V(LTQ_n)$ with $\vert L \cap V(L^{0j}) \vert =\vert L \cap V(R^{1j}) \vert =1$ for $j \in \{0, 1\}$. Then $LTQ_n$ contains $n-1$ internally disjoint L-trees.

Proof

Without loss of generality, let $a \in V(L^{00}), b \in V(L^{01}), d \in V(R^{10}), c \in V(R^{11})$. We further deal with the following cases.

Case 1. $\vert \{c'', d''\} \cap \{a, b\} \vert =0$.

By Definition 1, $\vert \{a'', b''\} \cap \{c, d\} \vert =0$. Without loss of generality, let $d'' \in V(L^{00})$ and $c'' \in V(L^{01})$. Since $L^0$ is $(n-1)$-connected, by Lemma 3, $L^0$ contains $(n-1)$ internally disjoint paths, denoted by $P_i$s, joining a and b, where $1 \le i \le n-1$.

Case 1.1. $(a, b) \notin E(L^0)$.

Note that $L^0$ is connected, there exists a path $P_0$ joining a and $d''$ and another path $P_0'$ joining b and $c''$. Denote the first node of $P_0 \cap \cup _{i=1}^{n-1}P_i$ by v and the first node of $P_0' \cap \cup _{i=1}^{n-1}P_i$ by $v'$. Without loss of generality, if v and $v'$ are in the same path, assume that $v, v' \in P_{n-1}$, otherwise suppose that $v \in P_{n-1}$ and $v' \in P_{n-2}$. Denote P the subpath joining $d''$ and v and $P'$ the subpath joining $c''$ and $v'$.

Select nodes, denoted by $u_1, \ldots , u_{n-3}$, in $P_1, \ldots , P_{n-3}$, respectively. By Definition 1 and Lemma 6, $u_i'' \in V(R^{10})$ and $u_i''$ has a crossing neighbor $u_i^*$ in $R^{11}$, or $u_i'' \in V(R^{11})$ and $u_i''$ has a crossing neighbor $u_i^*$ in $R^{10}$, where $1 \le i \le n-3$. Without loss of generality, denote $u_1'' \in V(R^{10})$ and $u_{n-3}'' \in V(R^{11})$. Then $u_1^* \in V(R^{11})$ and $u_{n-3}^* \in V(R^{10})$. Let $U''=\{a'', u_1'', \ldots , u_{n-3}^*\}$ and $U^*=\{b'', u_1^*, \ldots , u_{n-3}''\}$. Note that $R^{10}$ and $R^{11}$ are $(n-2)$-connected, by Lemma 4, there exist $(d, U'')$-paths, denoted by $Q_1, \ldots , Q_{n-3}, Q_{n-2}$, in $R^{10}$ and $(c, U^*)$-paths, denoted by $R_1, \ldots , R_{n-3}, R_{n-2}$, in $R^{11}$, where $Q_1$ joins d and $u_1''$, $\ldots$, $Q_{n-3}$ joins d and $u_{n-3}^*$, $Q_{n-2}$ joins d and $a''$, and $R_1$ joins c and $u_1^*$, $\ldots$, $R_{n-3}$ joins c and $u_{n-3}''$, $R_{n-2}$ joins c and $b''$. Let $T_i=P_i \cup (u_i, u_i'') \cup Q_i \cup R_i \cup (u_i'', u_i^*)$ for $1 \le i \le n-3$.

If $v, v' \in P_{n-1}$, let $T_{n-2}=P_{n-2} \cup (a, a'') \cup Q_{n-2} \cup (b, b'') \cup R_{n-2}$ and $T_{n-1}=P_{n-1} \cup P \cup (d'', d) \cup P' \cup (c'', c)$ (See Fig. 8a).

If $v' \in P_{n-2}$ and $v \in P_{n-1}$, let $T_{n-2}=P_{n-2} \cup (a, a'') \cup Q_{n-2} \cup P' \cup (c'', c)$ and $T_{n-1}=P_{n-1} \cup P \cup (d'', d) \cup (b, b'') \cup R_{n-2}$. (See 8 (b).)

Fig. 8

(a) $u, v' \in P_{n-1}$; (b) $v' \in P_{n-2}$ and $v \in P_{n-1}$

• Case 1.2. $(a, b) \in E(L^0)$.

By Definition 2, $(a'', b'') \in V(R^1)$ and $\vert \{a'', b''\} \cap V(R^{1i}) \vert =1$ for $i=0$ or 1. Suppose that $a'' \in V(R^{10})$ and $b'' \in V(R^{11})$.

• Case 1.2.1 $\vert \{d'', c''\} \cap V(L^{0i}) \vert =1$ for $i=0$ or 1.

Assume that $d'' \in V(L^{00})$ and $c'' \in V(L^{01})$. By Lemma 8, there are 3-paths, denoted by $\langle u_i'', u_i, v_i, v_i'' \rangle$s, in $LTQ_n$, where $u_i'' \in V(R^{10})$, $u_i \in V(L^{00})$, $v_i \in V(L^{01})$, $v_i'' \in V(R^{11})$, and $2 \le i \le n-2$. Let $U=\{d'', u_2, \ldots , u_{n-2}\}, U''=\{a'', u_2'', \ldots , u_{n-2}''\}, V=\{c'', v_2, \ldots , v_{n-2}\}$ and $V''=\{b'', v_2'', \ldots , v_{n-2}''\}$. By Lemma 4, there exist (a, U)-paths, denoted by $P_1, P_2, \ldots , P_{n-2}$, in $L^{00}$, $(d, U'')$-paths, denoted by $R_1, R_2, \ldots , R_{n-2}$, in $R^{10}$, (b, V)-paths, denoted by $Q_1, Q_2, \ldots , Q_{n-2}$, in $L^{01}$, and $(c, V'')$-paths, denoted by $S_1, S_2, \ldots , S_{n-2}$, in $R^{11}$, where $P_1$ joins a and $d''$, $P_i$ joins a and $u_i$, $R_1$ joins d and $a''$, $R_i$ joins d and $u_i''$, $Q_1$ joins b and $c''$, $Q_i$ joins b and $v_i$, $S_1$ joins c and $b''$, and $S_i$ joins c and $v_i''$, where $2 \le i \le n-2$. Let $T_1=(a, a'') \cup (a'', b'') \cup R_1 \cup (b, b'') \cup S_1$, $T_i=P_i \cup (u_i, u_i'') \cup R_i \cup (u_i, v_i) \cup Q_i \cup (v_i, v_i'') \cup S_i$ ($2 \le i \le n-2$), $T_{n-1}=(d, d'') \cup P_1 \cup (a, b) \cup Q_1 \cup (c'', c)$ (See Fig. 9a).

Fig. 9

(a) $\vert \{d'', c''\} \cap V(L^{0i}) \vert =1$ for $i=0$ or 1; (b) $\vert \{d'', c''\} \cap V(L^{0i}) \vert =2$ for $i=0$ or 1

• Case 1.2.2. $\vert \{d'', c''\} \cap V(L^{0i}) \vert =2$ for $i=0$ or 1.

Suppose that $\vert \{d'', c''\} \cap V(L^{00}) \vert =2$. (Note that in this case, $(d, c) \notin E(LTQ_n)$, otherwise by Definition 2$\vert \{d'', c''\} \cap V(L^{00}) \vert =1$.) Denote the crossing neighbor of c in $R^{10}$ by $c'$ and the crossing neighbor of $c''$, $d''$ in $L^{01}$ by $c^*$ and $d^*$ respectively. By Lemma 8, there exist 3-paths $\langle u_i'', u_i, v_i, v_i'' \rangle$s in $LTQ_n$, where $u_i'' \in V(R^{10}), u_i \in V(L^{00}), v_i \in V(L^{01})$, $v_i'' \in V(R^{11})$, and $2 \le i \le n-3$. Denote $U=\{d'', u_2, \ldots , u_{n-3}, c''\}$, $U''=\{a'', u_2'', \ldots , u_{n-3}'', c'\}$, $V=\{d^*, v_2, \ldots , v_{n-3}, c^*\}$, and $V''=\{b'', v_2'', \ldots , v_{n-3}'', d'\}$. Note that $L^{0j}$ and $R^{1j}$ are $(n-2)$-connected for $j \in \{0, 1\}$, by Lemma 4, $L^{00}$ contains (a, U)-paths, denoted by $P_1, P_2, \ldots , P_{n-3}, P_{n-2}$, $L^{01}$ contains (b, V)-paths, denoted by $Q_1, Q_2, \ldots , Q_{n-3}, Q_{n-2}$, $R^{10}$ contains $(d, U'')$-paths, denoted by $R_1, R_2, \ldots , R_{n-3}, R_{n-2}$, and $R^{11}$ contains $(c, V'')$-paths, denoted by $S_1, S_2, \ldots , S_{n-3}, S_{n-2}$, where $P_1$ joins a and $d''$, $P_i$ joins a and $u_i$, $P_{n-2}$ joins a and $c''$, $Q_1$ joins b and $d^*$, $Q_i$ joins b and $v_i$, $Q_{n-2}$ joins b and $c^*$, $R_1$ joins d and $a''$, $R_i$ joins d and $u_i''$, $R_{n-2}$ joins d and $c'$, $S_1$ joins c and $b''$, $S_i$ joins c and $v_i''$, $S_{n-2}$ joins c and $d'$, where $2 \le i \le n-3$. Let $T_1=R_1 \cup (a'', a) \cup (a, b) \cup (b, b'') \cup S_1$, $T_i=R_i \cup (u_i'', u_i) \cup P_i \cup (u_i, v_i) \cup Q_i \cup (v_i, v_i'') \cup S_i$ for $2 \le i \le n-3$, $T_{n-2}=R_{n-2} \cup (c', c) \cup (c, c'') \cup P_{n-2} \cup (c'', c^*) \cup Q_{n-2}$, and $T_{n-1}=P_1 \cup (d'', d) \cup (d, d') \cup S_{n-2} \cup (d'', d^*) \cup Q_1$ (See Fig. 9b).

• Case 2. $\vert \{d'', c''\} \cap \{a, b\} \vert =1$.

Without loss of generality, let $d''=a$ and $c'' \ne b$. Since $L^0$ is $(n-1)$-connected, by Lemma 3, $L^0$ contains $(n-1)$ internally disjoint paths joining a and b, denoted by $P_1, \ldots , P_{n-2}, P_{n-1}$. (If $d' \ne c$ and $(a, b) \in E(L^0)$, we assume that $P_{n-2}=(a, b)$, and if $d'=c$ and $(a, b) \in E(L^0)$, we assume that $P_{n-1}=(a, b)$.) Since $L^0$ is $(n-1)$-connected, $L^0$ contains a path $P_0$ joining $c''$ and b. Denote the first node of $P_0 \cap \cup _{i=1}^{n-1}P_i$ by v. Suppose that $v \in V(P_{n-1})$. Denote the subpath joining $c''$ and v by P. Select nodes, denoted by $u_1, \ldots , u_{n-3}$ in $P_1, \ldots , P_{n-3}$ respectively. By Lemma 6, $u_i''$ may be in $R^{10}$ or $R^{11}$. Assume that $u_i'' \in V(R^{10})$ for $1 \le i \le n-3$. Hence $u_i^* \in V(R^{11})$ for $1 \le i \le n-3$.

• Case 2.1. $d' \ne c$.

Let $U''=\{u_1'', \ldots , u_{n-3}'', c'\}$ and $U^*=\{u_1^*, \ldots , u_{n-3}^*, d'\}$. Since $R^{10}$ and $R^{11}$ are $(n-2)$-connected, by Lemma 4, there exist $(d, U'')$-paths, denoted by $Q_1, \ldots , Q_{n-3}, Q_{n-2}$, in $R^{10}$, and there exist $(c, U^*)$-paths, denoted by $R_1, \ldots , R_{n-3}, R_{n-2}$, in $R^{11}$, where $Q_i$ joins d and $u_i''$, $Q_{n-2}$ joins d and $c'$, $R_i$ joins c and $u_i^*$, and $R_{n-2}$ joins c and $d'$, where $1 \le i \le n-3$. Let $T_i=P_i \cup (u_i, u_i'') \cup Q_i \cup (u_i'', u_i^*) \cup R_i$ ($1 \le i \le n-3$), $T_{n-2}=P_{n-2} \cup (a, d) \cup (d, d') \cup R_{n-2}$, $T_{n-1}=P_{n-1} \cup P \cup (c'', c) \cup (c, c') \cup Q_{n-2}$ (See Fig. 10a).

• Case 2.2. $d'=c$.

Pick one node, denoted by $u_{n-2}$, in $P_{n-2}$. Without loss of generality, let $u_{n-2}'' \in V(R^{10})$. Let $u_{n-2}^*$ be the crossing neighbor of $u_{n-2}''$ in $R^{11}$. Let $U''=\{u_1'', \ldots , u_{n-2}''\}$ and $U^*=\{u_1^*, \ldots , u_{n-2}^*\}$. Since $R^{10}$ and $R^{11}$ are $(n-2)$-connected, there exist $(d, U'')$-paths, denoted by $Q_1, \ldots , Q_{n-2}$, in $R^{10}$, and $(c, U^*)$-paths, denoted by $R_1, \ldots , R_{n-2}$, in $R^{11}$, where $Q_i$ joins d and $u_i''$, $R_i$ joins c and $u_i^*$, and $1 \le i \le n-2$. Let $T_i=P_i \cup (u_i, u_i'') \cup Q_i \cup (u_i'', u_i^*) \cup R_i$ ($1 \le i \le n-2$), $T_{n-1}=P_{n-1} \cup (a, d) \cup (d, c)$ (See Fig. 10b).

Fig. 10

(a) $d' \ne c$; (b) $d'=c$

• Case 3. $\vert \{d'', c''\} \cap \{a, b\} \vert =2$.

By Lemma 6, without loss of generality, let $d''=a$ and $c''=b$. The proof of this case is similar to Case 2.2, except that we need to let $T_{n-1}=P_{n-1} \cup (a, d) \cup (b, c)$. So the lemma holds.$\square$

The following is our main result.

Theorem 1

$\kappa _4(LTQ_n)=n-1$, where $n \ge 2$.

Proof

By Lemma 2 and $LTQ_n$ is n-regular, $\kappa _4(LTQ_n) \le n-1$. We will show that $\kappa _4(LTQ_n) \ge n-1$. For any node set L, denoted by $L=\{a, b, d, c\}$, we will construct $n-1$ internally disjoint L-trees. Take induction hypothesis on n. By Lemmas 9 and 10, the theorem is correct for $n \in \{2, 3\}$. Suppose that the theorem is correct when $k<n$. We consider $k=n \ge 4$ as follows. By the symmetry of $L^0$ and $R^1$, we divide the following situations.

• Case 1. $\vert L \cap V(L^0) \vert =4$.

By the induction hypothesis, $L^0$ contains $n-2$ L-trees, denoted by $T_i$s ($1 \le i \le n-2$). By Definition 1, $(a, a''), (b, b''), (c, c''), (d, d'')$ are crossing edges between $L^0$ and $R^1$. Since $R^1$ is connected, $R^1$ contains a tree, denoted by $T_{n-1}'$, joining $a'', b'', c'', d''$. Denote $T_{n-1}=T_{n-1}' \cup (a, a'') \cup (b, b'') \cup (c, c'') \cup (d, d'')$. Hence, $T_i$s ($1 \le i \le n-1$) are $n-1$ desired L-trees.

• Case 2. $\vert L \cap V(L^0) \vert =3$ and $\vert L \cap V(R^1) \vert =1$.

• Case 3. $\vert L \cap V(L^0) \vert =\vert L \cap V(R^1) \vert =2$.

By symmetry of $L^0$ and $R^0$, $L^{00}$ and $L^{01}$, and $R^{10}$ and $R^{11}$, we only need to consider the following cases.

• Case 3.1. $\vert L \cap V(L^{00}) \vert =\vert L \cap V(R^{10})\vert =2$.

• Case 3.2. $\vert L \cap V(L^{00}) \vert =\vert L \cap V(L^{01}) \vert =1$ and $\vert L \cap V(R^{10}) \vert =2$.

• Case 3.3. $\vert L \cap V(L^{0j}) \vert =\vert L \cap V(R^{1j}) \vert =1$, where $j \in \{0, 1\}$.

By Lemmas 11, 13, 14, 15, there exist $n-1$ internally disjoint L-trees for the above Cases 2, 3.1, 3.2, 3.3 respectively.

So the theorem holds. $\square$

4 Conclusion

In [41], it has been proved that $\kappa _3(LTQ_n)=n-1$ ($n \ge 2$). In this paper, it is further shown that $\kappa _4(LTQ_n)=n-1$ ($n \ge 2$). Since $LTQ_n$ is n-regular and $\kappa (LTQ_n) \le \delta (LTQ_n)-1$, this result is optimal. Our further research is to extend our method of this paper to some special n-regular graphs.