Two-Disjoint-Cycle-Cover Pancyclicity of Augmented Cubes

Abstract

A graph G is two-disjoint-cycle-cover $[r_{1},r_{2}]$-pancyclic, if for any integer $\ell$ satisfying $r_{1} \leqslant \ell \leqslant r_{2}$, there exist two vertex-disjoint cycles $C_{1}$ and $C_{2}$ in G such that the lengths of $C_{1}$ and $C_{2}$ are $\ell$ and $|V(G)|-\ell$, respectively, where |V(G)| denotes the number of vertices in G. More specifically, a graph G is two-disjoint-cycle-cover vertex $[r_{1},r_{2}]$-pancyclic (resp. edge $[r_{1},r_{2}]$-pancyclic) if for any two distinct vertices $u_{1}, u_{2} \in V(G)$ (resp. two vertex-disjoint edges $e_{1}, e_{2} \in E(G)$), there exist two vertex-disjoint cycles $C_{1}$ and $C_{2}$ in G such that for every integer $\ell$ satisfying $r_{1} \leqslant \ell \leqslant r_{2}$, $C_{1}$ contains $u_{1}$ (resp. $e_{1}$) with length $\ell$ and $C_{2}$ contains $u_{2}$ (resp. $e_{2}$) with length $|V(G)|-\ell$. In this paper, we consider the problem of two-disjoint-cycle-cover pancyclicity of the n-dimensional augmented cube $AQ_n$ and obtain the following results: $AQ_n$ is two-disjoint-cycle-cover $[3,2^{n-1}]$-pancyclic for $n \geqslant 3$. Moreover, $AQ_n$ is two-disjoint-cycle-cover vertex $[3,2^{n-1}]$-pancyclic for $n \geqslant 3$, and $AQ_n$ is two-disjoint-cycle-cover edge $[4,2^{n-1}]$-pancyclic for $n \geqslant 3$.

Appendix

In this section, we will complete the proof of Lemmas 5, 6 and 7.

Lemma 5

The n-dimensional augmented cube $AQ_{n}$ $has$ $a$ $paired$ $two$-$disjoint$ $path$ $cover$ $joining$ $X=\{ x_1, x_2\}$ $and$ $Y=\{ y_1, y_2\}$ $for$ $n \geqslant 2$.

Proof

As $n=2$, it can be easily seen that $AQ_{2}$ has a paired 2-disjoint path cover joining $X=\{ x_1, x_2\}$ and $Y=\{ y_1, y_2\}$. Since $AQ_{2}$ is a complete graph $K_4$, $x_i$ is adjacent to $y_i$ for $i=1,2$.

As $n=3$, for any two pairs of four distinct vertices $X=\{ x_1, x_2\}$ and $Y=\{ y_1, y_2\}$ of $AQ_{3}$. Without loss of generality, we need to discuss the following cases in $AQ_3$.

Case 1 $\{x_1,x_2 \} \subseteq V(AQ_{2}^{0})$ and $\{y_1,y_2 \} \subseteq V(AQ_{2}^{0})$.

Since $AQ_{2}$ is a complete graph $K_4$, for $x_1^h, x_2^h, y_1^h, y_2^h \in V(AQ_{2}^{1})$, we have $x_1^h$ is adjacent to $y_1^h$ and $x_2^h$ is adjacent to $y_2^h$. Let $P_1=\langle x_{1},x_{1}^{h}, y_1^h, y_1 \rangle$, $P_2=\langle x_{2}, x_{2}^{h}, y_2^h, y_2 \rangle$; then, $P_1$ is a $(x_1,y_1)$-path, $P_2$ is a $(x_2,y_2)$-path such that $V(P_1) \cap V(P_2)= \varnothing$, and $V(P_1) \cup V(P_2)= V(AQ_{3})$.

Case 2 $\{x_1,x_2,y_1 \} \subseteq V(AQ_{2}^{0})$, $\{y_2 \} \subseteq V(AQ_{2}^{1})$.

Assume that $V(AQ_{2}^{0})= \{ x_1,x_2, y_1, w\}$, since w has two neighbors in $AQ_{2}^{1}$, the vertex w has a neighbor $w'$ in $V(AQ_{2}^{1})-\{y_2 \}$. Since $AQ_{2}$ is Hamiltonian connected, there exists a Hamiltonian path P joining $w'$ and $y_2$ in $AQ_{2}^1$. Hence, $P_1=\langle x_{1}, y_1 \rangle$ and $P_2=\langle x_{2}, w, w', P, y_2 \rangle$ are the vertex-disjoint paths required.

Case 3 $\{x_1,x_2 \} \subseteq V(AQ_{2}^{0})$ and $\{y_1,y_2 \} \subseteq V(AQ_{2}^{1})$.

If $x_1 \sim y_1$ or $x_2 \sim y_2$. Let $V(AQ_{2}^{0})= \{ x_1,x_2, a, b\}$, without loss of generality, we assume that $x_1 \sim y_1$. Then, there exists a vertex in $\{a, b\}$ such that it has neighbors in $V(AQ_2^1)-\{y_1, y_2\}$. (Otherwise, both a and b are adjacent to $y_1$, $y_1$ has 3 neighbors in $AQ_2^0$, a contradiction!) Assume that a has a neighbor $a'$ in $V(AQ_2^1)-\{y_1, y_2\}$, and $V(AQ_{2}^{1})= \{ y_1,y_2, a', c\}$. Since $AQ_{2}$ is a complete graph $K_4$, $P_1=\langle x_{1}, y_1 \rangle$, $P_2=\langle x_{2}, b, a, a', c, y_2 \rangle$ are the vertex-disjoint paths required.

If $x_1 \not \sim y_1$ and $x_2 \not \sim y_2$. Assume that $V(AQ_{2}^{0})= \{ x_1,x_2, a, b\}$, $V(AQ_{2}^{1})= \{ y_1,y_2, c, d\}$. Since $x_1 \not \sim y_1$, there exists a neighbor of $x_1$ in $\{ c, d\}$. Without loss of generality, we assume that $x_1 \sim d$. $\langle x_{1}, d, c, y_1 \rangle$ is a 4-path. For a similar reason, there exists a neighbor of $y_2$ in $\{ a, b\}$, and we assume that $y_2 \sim b$. $\langle x_{2}, a, b, y_2 \rangle$ is a 4-path. Hence, $P_1=\langle x_{1}, d, c, y_1 \rangle$ and $P_2=\langle x_{2}, a, b, y_2 \rangle$ are the vertex-disjoint paths required.

Case 4 $\{x_1,y_1 \} \subseteq V(AQ_{2}^{0})$, $\{x_2,y_2 \} \subseteq V(AQ_{2}^{1})$.

Since both $AQ_{2}^0$ and $AQ_{2}^1$ are Hamiltonian connected, there exists a Hamiltonian path $P_1$ joining $x_1$ and $y_1$ in $AQ_{2}^0$ and a Hamiltonian path $P_2$ joining $x_2$ and $y_2$ in $AQ_{2}^1$. Thus, $P_1$ and $P_2$ are the vertex-disjoint paths required.

Case 5 $\{x_1,y_2 \} \subseteq V(AQ_{2}^{0})$, $\{x_2,y_1 \} \subseteq V(AQ_{2}^{1})$.

If $x_1 \sim y_1$ or $x_2 \sim y_2$. Let $V(AQ_{2}^{0})= \{ x_1,y_2, a, b\}$; without loss of generality, we assume that $x_1 \sim y_1$. Then, there exists a vertex in $\{a, b\}$ such that it has neighbors in $V(AQ_2^1)-\{x_2, y_1\}$. (Otherwise, both a and b are adjacent to $y_1$, $y_1$ has 3 neighbors in $AQ_2^0$, a contradiction!) Assume that a has a neighbor $a'$ in $V(AQ_2^1)-\{x_2, y_1\}$, and $V(AQ_{2}^{1})= \{ x_2, y_1, a', c\}$. Since $AQ_{2}$ is a complete graph $K_4$, $P_1=\langle x_{1}, y_1 \rangle$, $P_2=\langle x_{2}, c, a', a, b, y_2 \rangle$ are the vertex-disjoint paths required.

If $x_1 \not \sim y_1$ and $x_2 \not \sim y_2$. Assume that $V(AQ_{2}^{0})= \{ x_1,y_2, a, b\}$, $V(AQ_{2}^{1})= \{ x_2,y_1, c, d\}$. Since $x_1 \not \sim y_1$, there exists a neighbor of $x_1$ in $\{ c, d\}$. Without loss of generality, we assume that $x_1 \sim d$. $\langle x_{1}, d, c, y_1 \rangle$ is a 4-path. For a similar reason, there exists a neighbor of $x_2$ in $\{ a, b\}$, and we assume that $x_2 \sim b$. $\langle x_{2}, b, a, y_2 \rangle$ is a 4-path. Hence, $P_1=\langle x_{1}, d, c, y_1 \rangle$ and $P_2=\langle x_{2}, b, a, y_2 \rangle$ are the vertex-disjoint paths required.

For $n\geqslant 4$, Lemma 4 has already been proven. This completes the proof of Lemma 5.

Lemma 6

The augmented cube $AQ_{3}$ $is$ $two$-$disjoint$-$cycle$-$cover$ $edge$ $\{4\}$-$pancyclic$.

Proof

For every two vertex-disjoint edges $(u, v), (x, y) \in E(AQ_3)$, without loss of generality, we assume that $u \in V(AQ_{2}^0)$, and $x \in V(AQ_{2}^0)$ if (x, y) is a hypercube edge or a complement edge. Then, all possibilities of $\{ u, v, x, y \}$ can be divided into the following five cases:

Case 1 $\{u, v, x, y \} \subseteq V(AQ_{2}^{0})$.

Since $(u, v), (x, y) \in E(AQ_{2}^{0})$, $(u^h, v^h), (x^h, y^h) \in E(AQ_{2}^{1})$. Let $R=\langle u, v, v^h, u^h, u \rangle$ and $S=\langle x, y, y^h, x^h, x \rangle$; then, R and S are the required vertex disjoint 4-cycles.

Case 2 $\{u, v, x \} \subseteq V(AQ_{2}^{0})$ and $\{y \} \subseteq V(AQ_{2}^{1})$.

Assume that $V(AQ_{2}^{0})=\{u, v, x, w \}$; since $AQ_{2}$ is a complete graph $K_4$, we have $x \sim w$. Because x is adjacent to y, without loss of generality, we assume that $y=x^h$. Then, $u^h, v^h, y, w^h$ are four distinct vertices in $AQ_{2}^{1}$, and $(u^h, v^h), (y, w^h) \in E(AQ_{2}^{1})$. Hence, $R=\langle u, v, v^h, u^h, u \rangle$ and $S=\langle x, y, w^h, w, x \rangle$ are the required 4-cycles.

Case 3 $\{u, x, y \} \subseteq V(AQ_{2}^{0})$ and $\{v \} \subseteq V(AQ_{2}^{1})$.

We can obtain the result in this case by a proof similar to Case 2.

Case 4 $\{u, v \} \subseteq V(AQ_{2}^{0})$ and $\{x, y \} \subseteq V(AQ_{2}^{1})$.

Since both $AQ_{2}^0$ and $AQ_{2}^1$ are Hamiltonian connected, there exists a Hamiltonian path $P_1$ joining u and v in $AQ_{2}^0$ and a Hamiltonian path $P_2$ joining x and y in $AQ_{2}^1$. Hence, $R= \langle u, P_1, v, u \rangle$ and $S=\langle x, P_2, y, x \rangle$ are the required 4-cycles.

Case 5 $\{u, x \} \subseteq V(AQ_{2}^{0})$ and $\{v, y \} \subseteq V(AQ_{2}^{1})$.

If u is adjacent to y. Since v and y are neighbors of u in $AQ_{2}^{1}$, without loss of generality, we assume that $v=u^h$, $y=u^c$. Then, $y=x^h$. We assume that $V(AQ_{2}^{0})=\{u, x, w, z \}$. Since $AQ_{2}$ is a complete graph, $R=\langle u, v, w^h, w, u \rangle$ and $S=\langle x, y, z^h, z, x \rangle$ are the required 4-cycles.

If u is not adjacent to y. Since u has two neighbors in $AQ_{2}^{1}$, there exists a vertex a in $V(AQ_{2}^{1})-\{v, y \}$ such that $a \sim u$. We assume that $V(AQ_{2}^{1})=\{v, y, a, b \}$. Since $AQ_{2}$ is a complete graph, $b \sim v$ and $b \sim a$. For the same reason, there exists a vertex c in $V(AQ_{2}^{0})-\{u, x \}$ such that $c \sim y$. We assume that $V(AQ_{2}^{0})=\{u, x, c, d \}$; then, $d \sim x$ and $d \sim c$. Hence, $R=\langle u, v, b, a, u \rangle$ and $S=\langle x, y, c, d, x \rangle$ are the required 4-cycles.

This completes the proof of Lemma 6.

Lemma 7

The augmented cube $AQ_{4}$ $is$ $two$-$disjoint$-$cycle$-$cover$ $edge$ $[4, 8 ]$-$pancyclic$.

Proof

First, we will make a claim below, which will be used in the proof of Lemma 7.

Claim$For \ every \ two\ vertex$-$disjoint\ edges$ $(u, v), (x, y) \in E(AQ_3)$, $there\ exists\ a\ Hamiltonian$ $path\ joining$ x $and$ y $in$ $AQ_3-\{u, v \}$, $moreover$, $there\ exists\ a\ cycle$ $C_5$ $contains$ (u, v) $in$ $AQ_3-\{x, y \}$ $with\ length$ 5 $and\ a\ path$ $P_3$ $contains$ (x, y) $with\ length$ 3 $in$ $AQ_3-C_5$, $except\ for\ the$ $situation$ $d(u, x)=d(u, y)=d(v, x)=d(v, y)=2$.

By Lemma 3, $AQ_3$ is vertex transitive; then, we put the vertex u in the position 000.

Case 1 $(u, v) \in \{ (000, 100), (000, 010), (000, 001), (000, 111) \}$.

First, for $e_1=(000, 100)$, $e_2=(000, 001)$, and $e_3=(000, 111)$, there exists $\varphi _i \in Aut(AQ_3), i=1, 2, 3$, such that $\varphi _i(e_i)=(000, 010), i=1, 2, 3$ (Table 1).

Table 1 The automorphisms $\varphi _i \in Aut(AQ_3), i=1, 2, 3$

Hence, we only need to consider the situation $(u, v)=(000, 010)$. Table 2 gives all possibilities of (x, y).

Table 2 The situation $(u, v)=(000, 010)$

Case 2 $(u, v)=(000, 011)$.

Obviously, when $(x, y)=(101, 110)$, we have $d(u, x)=d(u, y)=d(v, x)=d(v, y)=2$. Hence, Table 3 gives all possibilities of (x, y), except for $(x, y)=(101, 110)$.

Table 3 The situation $(u, v)=(000, 011)$

This completes the proof of Claim.

Now, we will prove Lemma 6. For every two vertex-disjoint edges $(u, v), (x, y) \in E(AQ_4)$, we need to prove that there exist two vertex-disjoint cycles $C_{\ell }$ and $C_{16-\ell }$ in $AQ_4$ such that for every integer $\ell$ satisfying $4 \leqslant \ell \leqslant 8$, $C_{\ell }$ contains (u, v) with length $\ell$, and $C_{16-\ell }$ contains (x, y) with length $16-\ell$.

Since $AQ_4$ is vertex transitive, we put vertex u in position 0000. Furthermore, there is an automorphism $\varphi$ of $AQ_4$, which is listed below such that $\varphi (0000, 0001)=(0000, 1111)$ (Table 4).

Table 4 The automorphisms $\varphi$

Then, all possibilities of $\{ u, v, x, y \}$ can be divided into the following three cases:

Case 1 $\{u, v, x, y \} \subseteq V(AQ_{3}^{0})$.

Subcase 1.1 $\ell =4$.

By Lemma 6, there exist two vertex-disjoint cycles R and S in $AQ_{3}^0$ such that R contains (u, v) with length 4, and S contains (x, y) with length 4. We denote S as $S=\langle x, a, b, y, x \rangle$; then, $a^h, b^h \in V(AQ_{3}^1)$. Since $AQ_{3}$ is Hamiltonian connected, there exists a Hamiltonian path P joining $a^h$ and $b^h$ in $AQ_{3}^1$. Hence, $C_{4}= R$ and $C_{12}=\langle x, a, a^h, P, b^h, b, y, x \rangle$ are the required cycles.

Subcase 1.2 $\ell =5$.

If $d(u, x)=d(u, y)=d(v, x)=d(v, y)=2$, under the isomorphism significance, we only need to consider the situation that $(u, v)=(0000, 0011)$, $(x, y)=(0101, 0110)$. Then, $C_{5}=\langle 0000, 0011, 0001, 1001, 1000, 0000 \rangle$ and $C_{11}=\langle 0101, 0110, 0100, 0111, 1111, 1101, 1110, 1100, 1011$, $1010, 0010, 0101\rangle$ are the required cycles.

Otherwise, by our claim, there exists a 5-cycle R containing (u, v) in $AQ_{3}^0-\{x, y \}$, and $AQ_{3}^0-R$ is connected. We assume that $V(AQ_{3}^0)-R=\{x, y, w \}$; then, w is connected with (x, y), and without loss of generality, we assume that $w \sim y$. Then, $x^h, w^h \in V(AQ_{3}^1)$, and there exists a Hamiltonian path P joining $x^h$ and $w^h$ in $AQ_{3}^1$. Hence, $C_{5}= R$ and $C_{11}=\langle x, y, w, w^h, P, x^h, x \rangle$ are the required cycles.

Subcase 1.3 $\ell =6$.

If $d(u, x)=d(u, y)=d(v, x)=d(v, y)=2$, under the isomorphism significance, we only need to consider the situation that $(u, v)=(0000, 0011)$, $(x, y)=(0101, 0110)$. Then, $C_{6}=\langle 0000, 0011, 0111, 1111, 1100, 0100, 0000 \rangle$ and $C_{10}=\langle 0101, 0110, 0010, 1010, 1000, 1011, 1001, 1101$, $1110, 0001, 0101\rangle$ are the required cycles.

Otherwise, by our claim, there exists a Hamiltonian path $P_1$ joining u and v in $AQ_{3}^0-\{x, y \}$. Since $x^h, y^h \in V(AQ_{3}^1)$, there exists a Hamiltonian path $P_2$ joining $x^h$ and $y^h$ in $AQ_{3}^1$. Hence, $C_{6}= \langle u, v, P_1, u \rangle$ and $C_{10}=\langle x, y, y^h, P_2, x^h, x \rangle$ are the required cycles.

Subcase 1.4 $\ell =7$.

If $d(u, x)=d(u, y)=d(v, x)=d(v, y)=2$, under the isomorphism significance, we only need to consider the situation that $(u, v)=(0000, 0011)$, $(x, y)=(0101, 0110)$. Then, $C_{7}=\langle 0000, 0011, 1011, 1000, 1001, 0001, 0010, 0000 \rangle$ and $C_{9}=\langle 0101, 0110, 0100, 1100, 1110, 1010, 1101$, $1111, 0111, 0101\rangle$ are the required cycles.

Otherwise, by our claim, there exists a 5-cycle R containing (u, v) in $AQ_{3}^0-\{x, y \}$, and $AQ_{3}^0-R$ is connected. We assume that $V(AQ_{3}^0)-R=\{x, y, w \}$; then, w is connected with (x, y), and without loss of generality, we assume that $w \sim y$. Then, $x^h, w^h \in V(AQ_{3}^1)$, and there exists a vertex a in $R-\{u, v \}$ such that $a^h \sim x^h$. This is because there are only two vertices in $AQ_{3}^1$ that are not adjacent to $x^h$, and $|V(R)-\{u, v \}|=3$. We choose (a, b) in $R-\{u, v \}$; then, $a^h, b^h \in V(AQ_{3}^1)$, and we denote the cycle R as $\langle u, R_1, a, b, R_2, v, u \rangle$. By our claim, there exists a Hamiltonian path P joining $x^h$ and $w^h$ in $AQ_{3}^1-\{a^h, b^h \}$. Hence, $C_{7}= \langle u, R_1, a, a^h, b^h, b, R_2, v, u \rangle$ and $C_{9}=\langle x, y, w, w^h, P, x^h, x \rangle$ are the required cycles.

Subcase 1.5 $\ell =8$.

By Lemma 6, there exist two vertex-disjoint cycles R and S in $AQ_3^0$ such that R contains (u, v) with length 4, and S contains (x, y) with length 4. Denote R and S as $R=\langle u, a, b, v, u \rangle$, $S=\langle x, c, d, y, x \rangle$. We choose $a^h, b^h, c^h, d^h \in V(AQ_{3}^1)$; then, $(a^h, b^h)$, $(c^h, d^h) \in$ $E(AQ_{3}^1)$. By using Lemma 6 again, there exist two vertex-disjoint cycles $R'$ and $S'$ in $AQ_{3}^1$ such that $R'$ contains $(a^h, b^h)$ with 4, and $S'$ contains $(c^h, d^h)$ with 4. We denote $R'$ and $S'$ as $R'=\langle a^h, R_1', b^h, a^h \rangle$ and $S'=\langle c^h, S_1', d^h, c^h \rangle$, respectively. Hence, $C_{8}=\langle u, a, a^h, R_1', b^h, b, v, u \rangle$ and $C_{8}'=\langle x, c, c^h, S_1', d^h, d, y, x \rangle$ are the required cycles.

Case 2 $\{u, v, x \} \subseteq V(AQ_{3}^{0}), \{y \} \subseteq V(AQ_{3}^{1})$.

Subcase 2.1 $\ell =4$.

There exists a neighbor a of x in $V(AQ_{3}^0)-\{u, v \}$. By Lemma 6, there exist two vertex-disjoint cycles R and S in $AQ_3^0$ such that R contains (u, v) with length 4, and S contains (x, a) with length 4. We denote S as $S=\langle x, S_1, a, x \rangle$. Since $y \sim x$, without loss of generality, we assume that $y=x^h$. Then, $a^h \in V(AQ_{3}^1)$, and there exists a Hamiltonian path P joining y and $a^h$ in $AQ_{3}^1$. Hence, $C_{4}= R$ and $C_{12}=\langle x, y, P, a^h, a, S_1, x \rangle$ are the required cycles.

Subcase 2.2 $\ell =5$.

By our claim, there exists a 2-path $\langle x, a, b\rangle$ starting from x such that there exists a 5-cycle R containing (u, v) in $AQ_3^0-\{x, a, b \}$. Since $y \sim x$, without loss of generality, we assume that $y=x^h$. Then, $b^h \in V(AQ_{3}^1)$, and there exists a Hamiltonian path P joining y and $b^h$ in $AQ_{3}^1$. Hence, $C_{5}= R$ and $C_{11}=\langle x, y, P, b^h, b, a, x \rangle$ are the required cycles.

Subcase 2.3 $\ell =6$.

We can find a common neighbor a of x and u in $V(AQ_{3}^0)-\{v \}$. By the lemmas claim, there exists a Hamiltonian path $P_1$ joining u and v in $AQ_{3}^0-\{x, a \}$. Since $y \sim x$, without loss of generality, we assume that $y=x^h$. Then, $a^h \in V(AQ_{3}^1)$, and there exists a Hamiltonian path $P_2$ joining y and $a^h$ in $AQ_{3}^1$. Hence, $C_{6}=\langle u, v, P_1, u \rangle$ and $C_{10}=\langle x, y, P_2, a^h, a, x \rangle$ are the required cycles.

Subcase 2.4 $\ell =7$.

By Lemma 4, $AQ_3$ is 1-fault-tolerant Hamiltonian connected; then, there exists a Hamiltonian path $P_1$ joining u and v in $AQ_{3}^0-\{x \}$. The vertex x has another neighbor in $AQ_{3}^1$, which we denote as w. Then, there exists a Hamiltonian path $P_2$ joining y and w in $AQ_{3}^1$. Hence, $C_{7}=\langle u, v, P_1, u \rangle$ and $C_{9}=\langle x, y, P_2, w, x \rangle$ are the required cycles.

Subcase 2.5 $\ell =8$.

There exists a neighbor a of x in $V(AQ_{3}^0)-\{u, v \}$. By Lemma 6, there exist two vertex-disjoint cycles R and S in $AQ_3^0$ such that R contains (u, v) with length 4, and S contains (x, a) with length 4. Denote R and S as $R=\langle u, v, c, b, u$ and $S=\langle x, S_1, a, x \rangle$, respectively. Since $y \sim x$, without loss of generality, we assume that $y=x^h$. We choose $a^h, b^h, c^h \in V(AQ_{3}^1)$; then, $(a^h, y)$, $(c^h, d^h) \in$ $E(AQ_{3}^1)$. By using Lemma 6 again, there exist two vertex-disjoint cycles $R'$ and $S'$ in $AQ_{3}^1$ such that $R'$ contains $(c^h, d^h)$ with 4, and $S'$ contains $(a^h, y^h)$ with 4. We denote $R'$ and $S'$ as $R'=\langle c^h, R_1', b^h, c^h \rangle$ and $S'=\langle a^h, S_1', y, a^h \rangle$, respectively. Hence, $C_{8}=\langle u, v, c, c^h, R_1', b^h, b, u \rangle$ and $C_{8}'=\langle x, y, S_1', a^h, a, S_1, x \rangle$ are the required cycles.

Case 3 $\{u, v\} \subseteq V(AQ_{3}^{0}), \{x, y \} \subseteq V(AQ_{3}^{1})$.

Subcase 3.1 $\ell =4$.

From Lemma 6, there exists a 4-cycle R containing (u, v) in $AQ_3^0$. By Lemma 4, $AQ_4$ is 4-fault-tolerant Hamiltonian connected. Then, there exists a Hamiltonian path P joining x and y in $AQ_{4}-R$. Hence, $C_{4}=R$ and $C_{12}=\langle x, y, P, x \rangle$ are the required cycles.

Subcase 3.2 $\ell =5$.

There exists a neighbor a of u in $V(AQ_{3}^0)-\{v \}$, and we choose (a, b) in $AQ_{3}^0-\{u, v \}$. By our claim, there exists a 5-cycle R containing (u, v) in $AQ_{3}^0-\{a, b \}$, and $AQ_{3}^0-R$ is connected. We assume that $V(AQ_{3}^0)-R=\{a, b, c \}$. Then, c is connected with (a, b), and without loss of generality, we assume that $c \sim b$. Thus, $\langle a, b, c \rangle$ is a 2-path.

Condition (a) $a \sim c$.

There exists a vertex in $\{a, b, c \}$ such that it has neighbors in $AQ_{3}^1-\{x, y \}$. Since $\langle a, b, c, a \rangle$ is a 3-cycle in this condition, without loss of generality, we assume that b has neighbors in $AQ_{3}^1-\{x, y \}$, and we denote its neighbor as $b'$.

(i) If $\{a^h, a^c \} \cap \{x, y \} \ne \varnothing$. We assume that $a \sim x$. Since $AQ_3$ is 1-fault-tolerant Hamiltonian connected, there exists a Hamiltonian path P joining y and $b'$ in $AQ_{3}^1- \{x \}$. Hence, $C_{5}=R$ and $C_{11}=\langle x, y, P, b', b, c, a, x \rangle$ are the required cycles.

(ii) If $\{a^h, a^c \} \cap \{x, y \} = \varnothing$. Then, a has neighbor $a'$ in $V(AQ_{3}^1)-\{x, y, b' \}$. By Lemma 5, there exist two disjoint paths $P_1$ and $P_2$ of $AQ_{3}^{1}$ such that $P_1$ joins $a'$ to x, $P_2$ joins $b'$ to y and $P_1 \cup P_2$ spans $AQ_{3}^{1}$. Hence, $C_{5}= R$ and $C_{11}=\langle x, y, P_2, b', b, c, a, a', P_1, x \rangle$ are the required cycles.

Condition (b) $a \not \sim c$.

Then, a and c have no common neighbors in $AQ_{3}^1$.

(i) If $\{a^h, a^c \} \cap \{x, y \} \ne \varnothing$. We assume that $a \sim x$. Then, there exists a neighbor $c'$ of c in $AQ_{3}^1- \{x, y \}$. Since $AQ_3$ is 1-fault-tolerant Hamiltonian connected, there exists a Hamiltonian path P joining y and $c'$ in $AQ_{3}^1- \{x \}$. Hence, $C_{5}=R$ and $C_{11}=\langle x, y, P, c', c, b, a, x \rangle$ are the required cycles.

(ii) If $\{a^h, a^c \} \cap \{x, y \} = \varnothing$. Then, a has neighbor $a'$ in $V(AQ_{3}^1)-\{x, y, c' \}$. By Lemma 5, there exist two disjoint paths $P_1$ and $P_2$ of $AQ_{3}^{1}$ such that $P_1$ joins $a'$ to x, $P_2$ joins $c'$ to y and $P_1 \cup P_2$ spans $AQ_{3}^{1}$. Hence, $C_{5}= R$ and $C_{11}=\langle x, y, P_2, c', c, b, a, a', P_1, x \rangle$ are the required cycles.

Subcase 3.3 $\ell =6$.

First, we can find a vertex a in $N_{AQ_3^0}(u)-\{v \}$ such that $\{a^h, a^c \} \ne \{x, y \}$. We choose a neighbor of a in $AQ_{3}^1- \{x, y \}$, which is denoted as $a'$, and choose (a, b) in $AQ_{3}^0-\{u, v \}$. By our claim, there exists a Hamiltonian path $P_1$ joining u and v in $AQ_{3}^0- \{a, b \}$.

If $\{b^h, b^c \} \cap \{x, y \} \ne \varnothing$. We assume that $b \sim x$. Since $AQ_3$ is 1-fault-tolerant Hamiltonian connected, there exists a Hamiltonian path $P_2$ joining y and $a'$ in $AQ_{3}^1- \{x \}$. Hence, $C_{6}=\langle u, v, P_1, u \rangle$ and $C_{10}=\langle x, y, P_2, a', a, b, x \rangle$ are the required cycles.

If $\{b^h, b^c \} \cap \{x, y \} = \varnothing$. Then, b has neighbor $b'$ in $V(AQ_{3}^1)-\{x, y, a' \}$. By Lemma 5, there exist two disjoint paths $P_2$ and $P_3$ of $AQ_{3}^{1}$ such that $P_2$ joins $a'$ to y, $P_3$ joins $b'$ to x and $P_2 \cup P_3$ spans $AQ_{3}^{1}$. Hence, $C_{6}=\langle u, v, P_1, u \rangle$ and $C_{10}=\langle x, y, P_2, a', a, b, b', P_3, x \rangle$ are the required cycles.

Subcase 3.4 $\ell =7$.

Since $|\{u, v, x^h, x^c, y^h, y^c \}| \leqslant 6$ and $|V(AQ_3^0)|=8$, there exists a vertex a in $AQ_{3}^0- \{u, v \}$ such that $\{a^h, a^c \} \cap \{x, y \} = \varnothing$. Since $AQ_3$ is 1-fault-tolerant Hamiltonian connected, there exists a Hamiltonian path $P_1$ joining u and v in $AQ_{3}^0- \{a \}$. By Lemma 5, there exist two disjoint paths $P_2$ and $P_3$ of $AQ_{3}^{1}$ such that $P_2$ joins $a^h$ to x, $P_3$ joins $a^c$ to y and $P_2 \cup P_3$ spans $AQ_{3}^{1}$. Hence, $C_{7}=\langle u, v, P_1, u \rangle$ and $C_{9}=\langle x, y, P_3, a^c, a, a^h, P_2, x \rangle$ are the required cycles.

Subcase 3.5 $\ell =8$.

Since both $AQ_{3}^0$ and $AQ_{3}^1$ are Hamiltonian connected, there exists a Hamiltonian path $P_1$ joining u and v in $AQ_{3}^0$ and a Hamiltonian path $P_2$ joining x and y in $AQ_{3}^1$. Hence, $C_{8}= \langle u, P_1, v, u \rangle$ and $C_{8}'=\langle x, P_2, y, x \rangle$ are the required cycles.

This completes the proof of Lemma 7.