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$.

1 Introduction

A graph G is an ordered pair (V(G), E(G)) consisting of a set of vertices V(G), and a set of edges $E(G)\subseteq \{(u,v)\mid (u,v)$ is an unordered pair of elements of $V(G)\}$. A path in G is a sequence of distinct vertices $\langle v_{0},v_{1},\cdots ,v_{n} \rangle$ such that two vertices are adjacent if they are consecutive in the sequence, and the path joining u and v is called a (u, v)-path. A cycle is a path with at least three vertices such that the last vertex is adjacent to the first vertex, represented as $\langle v_{0},v_{1},\cdots ,v_{n},v_{0} \rangle$. A path (resp. cycle) is a Hamiltonian path (resp. Hamiltonian cycle) of G if it spans G. We say that G is Hamiltonian if it has a Hamiltonian cycle, and is Hamiltonian connected if there is a Hamiltonian path for any two distinct vertices of G. A Hamiltonian graph G is k-fault-tolerant Hamiltonian if $G-F$ remains Hamiltonian for every $F \subset V(G) \cup E(G)$ with $|F| \leqslant k$. A graph G is k-fault-tolerant Hamiltonian connected if $G-F$ remains Hamiltonian connected for every $F \subset V(G) \cup E(G)$ with $|F| \leqslant k$. The notation $G-F$ denotes the subgraph obtained from G by deleting all vertices and edges of F.

An isomorphism from a graph G to a graph H is a bijective function $\varphi$: $V(G)\rightarrow V(H)$ such that for $u, v \in V(G)$, $(\varphi (u), \varphi (v)) \in E(H)$ if and only if $(u, v) \in E(G)$. An automorphism of a graph G is an isomorphism from G to itself. The group of all automorphisms of a graph G is called the automorphism group of G, denoted by Aut(G). A graph G is said to be vertex-transitive if Aut(G) acts transitively on V(G); that is, for any two vertices u, v, there exists an automorphism $\varphi : V(G) \rightarrow V(G)$ such that $\varphi (u)=v$.

A two-disjoint-path cover of a graph is a set of two disjoint paths that altogether cover every vertex of the graph. Suppose that there are a set of two sources $X=\{ x_1, x_2\}$ and a set of two sinks $Y=\{ y_1, y_2\}$ in a graph G such that $X \cap Y= \varnothing$. There exist two disjoint paths $P_1$ and $P_2$ of G such that $P_1$ joins $x_1$ to $y_1$, $P_2$ joins $x_2$ to $y_2$, and $P_1 \cup P_2$ spans G. This two-disjoint-path cover is called paired if each source $x_i$ is joined to a specific sink $y_i$. Otherwise, it is called unpaired.

A graph G is pancyclic if it contains a cycle of length $\ell$ for every $\ell \in [3,|V(G)|]$ (we let $[i,j]= \{ i,i+1,\cdots ,j \}$ for positive integers i, j with $i<j$), where |V(G)| denotes the number of vertices in G. More specifically, a graph G is called vertex-pancyclic (resp. edge-pancyclic) if every vertex (resp. edge) of G lies on an $\ell$-cycle for every $\ell \in [3,|V(G)|]$.

Kung and Chen [1, 2] raised the problem of simultaneously embedding more than one cycle that can span the whole graph. A two-disjoint-cycle-cover of a graph G is a collection of two vertex-disjoint cycles of G that just spans G. By extending this concept together with pancyclicity, a graph G is two-disjoint-cycle-cover $[r_{1},r_{2}]$ -pancyclic if for every 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. 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$.

The problem of two-disjoint-cycle-cover pancyclicity was studied for crossed cubes [1] and locally twisted cubes [2]. Moreover, the problem of two-disjoint-cycle-cover bipancyclicity was studied for balanced hypercubes [3] and the bipartite generalized hypercube [4].

In this paper, we focus on the two-disjoint-cycle-cover pancyclicity of augmented cubes $AQ_n$, which was first proposed by Choudum and Sunitha [5] in 2002. For augmented cubes, many basic properties have been attained, such as vertex-transitivity [5], Hamiltonian connectivity [6] and fault Hamiltonicity [6]. Our research obtains the following results:

Theorem 1

The n-dimensional augmented cube $AQ_{n}$ $is$ $two$-$disjoint$-$cycle$-$cover$ $edge$ $[4, 2^{n-1} ]$-$pancyclic$ $for$ $n \geqslant 3$.

Theorem 2

The n-dimensional augmented cube $AQ_{n}$ $is$ $two$-$disjoint$-$cycle$-$cover$ $vertex$ $[3,$ $2^{n-1} ]$-$pancyclic$ $for$ $n \geqslant 3$.

Theorem 3

The n-dimensional augmented cube $AQ_{n}$ $is$ $two$-$disjoint$-$cycle$-$cover$ $[3, 2^{n-1} ]$-$pancyclic$ $for$ $n \geqslant 3$.

From the definitions above, it can be seen that $r_{2} \leqslant \frac{|V(G)|}{2}$. Since $|V(AQ_{n})|=2^n$, our results are optimal in the sense that $r_{2}$ has attained the maximum possible value.

The rest of this paper is organized as follows. Section 2 introduces some necessary definitions and preliminary results of augmented cube $AQ_{n}$. Our main results will be proven in Sect. 3. Finally, the concluding remarks are given in Sect. 4, and some proofs are given in Appendix.

2 Terminology and Preliminaries

The n-bit binary string is denoted by $\{ 0,1 \} ^n$. For any binary bit $u_{i} \in \{ 0,1 \}$, let ${\bar{u}}_{i} \equiv u_i \oplus 1$, where $\oplus$ represents the modulo 2 addition. The formal definition of an n-dimensional augmented cube $AQ_{n}$ is provided as follows.

Definition 1

([5]) Let $n \geqslant 1$ be an integer. The augmented cube $AQ_{n}$ of dimension n has $2^n$ vertices, each labeled by an n-bit binary string $u_{n} \cdots u_{2}u_{1}$. $AQ_{1}$ is the graph $K_ 2$ with vertex set $\{ 0, 1 \}$. For $n \geqslant 2$, $AQ_{n}$ can be recursively built from two disjoint copies of $AQ_{n-1}$ and by adding $2 \times 2^{n-1}$ edges between the two as follows:

Let $AQ_{n-1}^{0}$ denote the graph obtained from one copy of $AQ_{n-1}$ by prefixing the label of each node with 0. Let $AQ_{n-1}^{1}$ denote the graph obtained from the other copy of $AQ_{n-1}$ by prefixing the label of each node with 1. A vertex $u=0u_{n-1} \cdots u_{2}u_{1}$ of $AQ_{n-1}^{0}$ is joined to a vertex $v=1v_{n-1} \cdots v_{2}v_{1}$ of $AQ_{n-1}^{1}$ if and only if either

(1) $u_i=v_i$ for every i satisfying $1 \leqslant i \leqslant n-1$; or

(2) $u_i={\bar{v}}_i$ for every i satisfying $1 \leqslant i \leqslant n-1$.

Fig. 1

Illustrations of $AQ_{1}$, $AQ_{2}$ and $AQ_{3}$

According to Definition 1, Fig. 1 illustrates $AQ_{1}$, $AQ_{2}$ and $AQ_{3}$. An alternative (and equivalent) definition of $AQ_{n}$ is provided in the following nonrecursive fashion:

Definition 2

([5]) Let $n \geqslant 1$ be an integer. The augmented cube $AQ_{n}$ of dimension n has $2^n$ vertices, each labeled by an n-bit binary string $u_{n} \cdots u_{2}u_{1}$. Any two vertices $u=u_{n} \cdots u_{2}u_{1}$ and $v=v_{n} \cdots v_{2}v_{1}$ of $AQ_{n}$ are adjacent if and only if there exists an integer l, $1 \leqslant l \leqslant n$, such that one of the following conditions is satisfied:

(1) $u_l={\bar{v}}_l$ and $u_i=v_i$ for any i, $i \ne l$.

(2) $u_i={\bar{v}}_i$ for $1 < i \leqslant l$, and $u_i=v_i$ otherwise.

By the definitions above, the augmented cube $AQ_{n}$ of dimension n is $(2n-1)$-regular. For every vertex $u=u_{n}u_{n-1} \cdots u_{2}u_{1}$ in $AQ_{n}$, we denote $u^h={\bar{u}}_{n}u_{n-1} \cdots$ $u_{2}u_{1}$ and $u^c={\bar{u}}_{n}{\bar{u}}_{n-1} \cdots {\bar{u}}_{2}{\bar{u}}_{1}$. Then, $(u, u^h)$ is called the hypercube edge, and $(u, u^c)$ is called the complement edge. The following lemmas can be derived directly from the definitions:

Lemma 1

([6]) Let u and v be any two vertices in $AQ_{n-1}^i (i=0, 1)$ with $n \geqslant 4$. Suppose that u and v are not adjacent; then, $u^h, u^c, v^h$ and $v^c$ are all distinct.

Lemma 2

([6]) Let $(u, v) \in E(AQ_{n-1}^0)$, then $(u^h, v^h) \in E(AQ_{n-1}^1)$ and $(u^c, v^c) \in E(AQ_{n-1}^1)$. Let $(x, y) \in E(AQ_{n-1}^1)$, then $(x^h, y^h) \in E(AQ_{n-1}^0)$ and $(x^c, y^c) \in E(AQ_{n-1}^0)$.

To prove our main theorem, we need to obtain more results, as shown below.

Lemma 3

([5]) For every $n \geqslant 1$, $AQ_n$ is vertex-transitive.

Lemma 4

([6]) For every $n \geqslant 4$, $AQ_n$ is $(2n-3)$-fault-tolerant Hamiltonian, $(2n-4)$-fault-tolerant Hamiltonian connected and has a two-disjoint-path cover. Particularly, $AQ_3$ is 2-fault-tolerant Hamiltonian, and 1-fault-tolerant Hamiltonian connected.

However, it can be easily checked that both $AQ_2$ and $AQ_3$ have two-disjoint-path covers, and the detail verification is presented in Appendix. Hence, we have

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$.

Moreover, other relevant literature on augmented cubes in recent years, please also refer to [7,8,9,10,11,12,13,14,15,16,17,18].

3 Main Results

In this section, we first discuss the two-disjoint-cycle-cover edge pancyclicity of $AQ_n$.

Lemma 6

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

Lemma 7

The augmented cube $AQ_4$ is a two-disjoint-cycle-cover edge $[4, 8 ]$-pancyclic.

The proofs of the above lemmas are given in Appendix.

Theorem 1

The n-dimensional augmented cube $AQ_{n}$ is a two-disjoint-cycle-cover edge $[4, 2^{n-1} ]$-pancyclic for $n \geqslant 3$.

Proof

We will prove the result by induction on n. By Lemmas 6 and 7, we show that the theorem holds as $n=3$ and $n=4$. For $n\geqslant 5$, we assume that $AQ_{n-1}$ is two-disjoint-cycle-cover edge $[4, 2^{n-2} ]$-pancyclic by the induction hypothesis.

For every two vertex-disjoint edges $(u, v), (x, y) \in E(AQ_n)$, without loss of generality, we assume that $u \in V(AQ_{n-1}^0)$, and $x \in V(AQ_{n-1}^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_{n-1}^{0})$.

Subcase 1.1 $4 \leqslant \ell \leqslant 2^{n-2}$.

By induction, there exist two vertex-disjoint cycles R and S in $AQ_{n-1}^0$ such that R contains (u, v) with length $\ell$, and S contains (x, y) with length $2^{n-1}-\ell$. Since $|S|\geqslant |R| \geqslant 4$, there exist two adjacent vertices $a, b \in V(S)$ $-\{x, y\}$ in S. Denote S as $S=\langle x, S_1, a, b, S_2, y, x \rangle$. We choose $a^h, b^h \in V(AQ_{n-1}^1)$; then, there exists a Hamiltonian path P joining $a^h$ and $b^h$ in $AQ_{n-1}^1$ since $AQ_{n-1}^1$ is connected to the Hamiltonian path. Hence, $C_{\ell }=R$ and $C_{2^n-\ell }=\langle x, S_1, a, a^h, P, b^h, b, S_2, y, x \rangle$ are the required cycles; see Fig. 2(a) for an illustration.

Subcase 1.2 $2^{n-2}+1 \leqslant \ell \leqslant 2^{n-1}$.

Let $\ell =\ell _1+\ell _2$, where $4 \leqslant \ell _1 \leqslant 2^{n-2}$ and $2^{n-2}-3 \leqslant \ell _2 \leqslant 2^{n-2}$. By induction, there exist two vertex-disjoint cycles R and S in $AQ_{n-1}^0$ such that R contains (u, v) with length $\ell _1$, and S contains (x, y) with length $2^{n-1}-\ell _1$. Since $4 \leqslant \ell _1 \leqslant 2^{n-2}$, there exist two adjacent vertices $a, b \in V(R)$ $-\{u, v\}$ in R, and two adjacent vertices $c, d \in V(S)-\{x, y\}$ in S. Denote R and S as $\langle u, R_1, a, b, R_2, v, u \rangle$ and $\langle x, S_1, c, d, S_2, y, x \rangle$, respectively. We choose $a^h, b^h, c^h, d^h \in V(AQ_{n-1}^1)$; then, $(a^h, b^h)$, $(c^h, d^h) \in$ $E(AQ_{n-1}^1)$ by Lemma 2. By induction, there exist two vertex-disjoint cycles $R'$ and $S'$ in $AQ_{n-1}^1$ such that $R'$ contains $(a^h, b^h)$ with length $\ell _2$, and $S'$ contains $(c^h, d^h)$ with length $2^{n-1}-\ell _2$. Denote $R'$ and $S'$ as $\langle a^h, R_1', b^h, a^h \rangle$ and $\langle c^h, S_1', d^h, c^h \rangle$, respectively. Hence, $C_{\ell }=\langle u, R_1, a, a^h, R_1', b^h, b, R_2, v, u \rangle$ and $C_{2^n-\ell }=\langle x, S_1, c, c^h, S_1', d^h, d, S_2, y, x \rangle$ are the required cycles; see Fig. 2(b) for an illustration.

Fig. 2

Illustrations of Case 1 in the proof of Theorem 3.3

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

Subcase 2.1 $4 \leqslant \ell \leqslant 2^{n-2}$.

First, the vertex x has $2n-3 \geqslant 7$ neighbors in $AQ_{n-1}^0$; then, we can find a vertex $a \in V(AQ_{n-1}^0)- \{u, v \}$ that is adjacent to x. By induction, there exist two vertex-disjoint cycles R and S in $AQ_{n-1}^0$ such that R contains (u, v) with length $\ell$, and S contains (x, a) with length $2^{n-1}-\ell$. We denote S as $S=\langle x, S_1, a, x \rangle$. Because $y \sim x$ and $y \in V(AQ_{n-1}^1)$, we have $y=x^h$ or $y=x^c$. Without loss of generality, we assume that $y=x^h$. We choose $a^h \in V(AQ_{n-1}^1)$, then, there exists a Hamiltonian path P joining $a^h$ and y in $AQ_{n-1}^1$, since $AQ_{n-1}^1$ is Hamiltonian connected by Lemma 4. Hence, $C_{\ell }=R$ and $C_{2^n-\ell }=\langle x, S_1, a, a^h, P, y, x \rangle$ are the required cycles; see Fig. 3(a) for an illustration.

Subcase 2.2 $2^{n-2}+1 \leqslant \ell \leqslant 2^{n-1}$.

Let $\ell =\ell _1+\ell _2$, where $4 \leqslant \ell _1 \leqslant 2^{n-2}$ and $2^{n-2}-3 \leqslant \ell _2 \leqslant 2^{n-2}$. By a process similar to Subcase 2.1, we can find a vertex $a \in N(x)\cap V(AQ_{n-1}^0)- \{u, v \}$. By induction, there exist two vertex-disjoint cycles R and S in $AQ_{n-1}^0$ such that R contains (u, v) with length $\ell _1$, and S contains (x, a) with length $2^{n-1}-\ell _1$. We denote S as $S=\langle x, S_1, a, x \rangle$. Since $|R| \geqslant 4$, there exist two adjacent vertices $b, c \in V(R)$ $-\{u, v\}$ in R, and we denote R as $R=\langle u, R_1, b, c, R_2, v, u \rangle$. Because $y \sim x$ and $y \in V(AQ_{n-1}^1)$, we have $y=x^h$ or $y=x^c$. Without loss of generality, we assume that $y=x^h$. Then, $a^h, b^h, c^h \in V(AQ_{n-1}^1)$, and $(a^h, y)$, $(b^h, c^h) \in$ $E(AQ_{n-1}^1)$. By induction, there exist two vertex-disjoint cycles $R'$ and $S'$ in $AQ_{n-1}^1$ such that $R'$ contains $(b^h, c^h)$ with length $\ell _2$, and $S'$ contains $(a^h, y)$ with length $2^{n-1}-\ell _2$. Denote $R'$ and $S'$ as $\langle b^h, R_1', c^h, b^h \rangle$ and $\langle a^h, S_1', y, a^h \rangle$, respectively. Hence, $C_{\ell }=\langle u, R_1, b, b^h, R_1', c^h, c, R_2, v, u \rangle$ and $C_{2^n-\ell }=\langle x, S_1, a, a^h, S_1', y, x \rangle$ are the required cycles; see Fig. 3(b) for an illustration.

Fig. 3

Illustrations of Case 2 in the proof of Theorem 3.3

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

Subcase 3.1 $\ell = 4$.

We can find a vertex $a \in N(u)\cap V(AQ_{n-1}^0)- \{x, y \}$. Without loss of generality, we assume that $v=u^h$. Then, $a^h \in V(AQ_{n-1}^1)$ and $(a^h, v) \in E(AQ_{n-1}^1)$. From Lemma 4, we know that $AQ_n$ is an $(2n-4)$-fault tolerant Hamiltonian connected as $n \geqslant 4$. Since $2n-4 \geqslant 6$ when $n \geqslant 5$, there exists a Hamiltonian path P joining x and y in $AQ_n-\{u, v, a, a^h \}$. Hence, $C_{\ell }=\langle u, a, a^h, v, u \rangle$ and $C_{2^n-\ell }=\langle x, P, y, x \rangle$ are the required cycles; see Fig. 4(a) for an illustration.

Subcase 3.2 $5 \leqslant \ell \leqslant 2^{n-2}+1$.

Let $\ell =\ell _1+1$, where $4 \leqslant \ell _1 \leqslant 2^{n-2}$. Without loss of generality, we assume that $v=u^h$. Then, $u^c \in V(AQ_{n-1}^1)$ and $u^c \sim u$. From Lemma 4, there exists a Hamiltonian path P joining x and y in $AQ_n^0-\{u \}$. Obviously, there exist two adjacent vertices a and b in $P- \{x, y \}$ such that $\{ a^h, b^h \} \cap \{u^c \} =\varnothing$. We denote P as $P=\langle x, P_1, a, b, P_2, y \rangle$. By induction, there exist two vertex-disjoint cycles R and S in $AQ_{n-1}^1$ such that R contains $(v, u^c)$ with length $\ell _1$, and S contains $(a^h, b^h)$ with length $2^{n-1}-\ell _1$. Denote R and S as $\langle v, R_1, u^c, v \rangle$ and $\langle a^h, S_1, b^h, a^h \rangle$, respectively. Hence, $C_{\ell }=\langle u, v, R_1, u^c, u \rangle$ and $C_{2^n-\ell }=\langle x, P_1, a, a^h, S_1, b^h, b, P_2, y, x \rangle$ are the required cycles; see Fig. 4(b) for an illustration.

Subcase 3.3 $2^{n-2}+2 \leqslant \ell \leqslant 2^{n-1}$.

Let $\ell =\ell _1+\ell _2$, where $4 \leqslant \ell _1 \leqslant 2^{n-2}$ and $2^{n-2}-2 \leqslant \ell _2 \leqslant 2^{n-2}$. We can find a vertex $a \in N(u)\cap V(AQ_{n-1}^0)- \{x, y \}$. By induction, there exist two vertex-disjoint cycles R and S in $AQ_{n-1}^0$ such that R contains (u, a) with length $\ell _1$, and S contains (x, y) with length $2^{n-1}-\ell _1$. There exist two adjacent vertices b and c in $S- \{x, y \}$, and we denote R and S as $\langle u, a, R_1, u \rangle$ and $\langle x, S_1, b, c, S_2, y, x \rangle$, respectively. Without loss of generality, we assume that $v=u^h$. Then, $a^h, b^h, c^h \in V(AQ_{n-1}^1)$ and $(a^h, v), (b^h, c^h) \in E(AQ_{n-1}^1)$. By induction, there exist two vertex-disjoint cycles $R'$ and $S'$ in $AQ_{n-1}^1$ such that $R'$ contains $(v, a^h)$ with length $\ell _2$, and $S'$ contains $(b^h, c^h)$ with length $2^{n-1}-\ell _2$. Denote $R'$ and $S'$ as $\langle v, R_1', a^h, v \rangle$ and $\langle b^h, S_1', c^h, b^h \rangle$, respectively. Hence, $C_{\ell }=\langle u, v, R_1', a^h, a, R_1, u \rangle$ and $C_{2^n-\ell }=\langle x, S_1, b, b^h, S_1', c^h, c, S_2, y, x \rangle$ are the required cycles; see Fig. 4(c) for an illustration.

Fig. 4

Illustrations of Case 3 in the proof of Theorem 3.3

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

Subcase 4.1 $4 \leqslant \ell \leqslant 2^{n-1}-4$.

Obviously, there exist two adjacent vertices a and b in $AQ_{n-1}^{0}- \{u, v \}$ such that $\{ a^h, b^h \} \cap \{x, y \} =\varnothing$. By induction, there exist two vertex-disjoint cycles R and S in $AQ_{n-1}^0$ such that R contains (u, v) with length $\ell$, and S contains (a, b) with length $2^{n-1}-\ell$. Denote S as $S=\langle a, b, S_1, a \rangle$. From Lemma 5, there exist two disjoint paths $P_1$ and $P_2$ of $AQ_{n-1}^{1}$ such that $P_1$ joins $a^h$ to x, $P_2$ joins $b^h$ to y and $P_1 \cup P_2$ spans $AQ_{n-1}^{1}$. Hence, $C_{\ell }= R$ and $C_{2^n-\ell }=\langle x, y, P_2, b^h, b, S_1, a, a^h, P_1, x \rangle$ are the required cycles; see Fig. 5(a) for an illustration.

Subcase 4.2 $\ell = 2^{n-1}-3$.

Obviously, there exists a vertex a in $AQ_{n-1}^{0}- \{u, v \}$ such that $\{ a^h, a^c \} \cap \{x, y \} =\varnothing$. For every path $\langle a, b, c \rangle$ with length 2 in $AQ_{n-1}^{0}- \{u, v \}$, by Lemma 4, there exists a Hamiltonian path $P_1$ joining u and v in $AQ_{n-1}^{0}- \{a, b, c \}$.

If $\{c^h, c^c \} \cap \{x, y \} \ne \varnothing$, without loss of generality, we assume that c is adjacent to y. From Lemma 4, there exists a Hamiltonian path $P_2$ joining x and $a^h$ in $AQ_{n-1}^{1}- \{y \}$. Hence, $C_{\ell }= \langle u, P_1, v, u \rangle$ and $C_{2^n-\ell }=\langle x, y, c, b, a, a^h, P_2, x \rangle$ are the required cycles; see Fig. 5(b) for an illustration.

If $\{ c^h, c^c \} \cap \{x, y \} = \varnothing$, by Lemma 5, there exist two disjoint paths $P_2$ and $P_3$ of $AQ_{n-1}^{1}$ such that $P_2$ joins $a^h$ to x, $P_3$ joins $c^h$ to y and $P_2 \cup P_3$ spans $AQ_{n-1}^{1}$. Hence, $C_{\ell }= \langle u, P_1, v, u \rangle$ and $C_{2^n-\ell }=\langle x, y, P_3, c^h, c, b, a, a^h, P_2, x \rangle$ are the required cycles; see Fig. 5(c) for an for illustration.

Subcase 4.3 $\ell = 2^{n-1}-2$.

For $|\{ u, v, x^h, x^c, y^h, y^c \}| \leqslant 6$, there exists an edge (a, b) in $AQ_{n-1}^0-\{u, v \}$ such that $\{ a^h, a^c, b^h$, $b^c \} \cap \{x, y \} =\varnothing$. By Lemma 4, there exists a Hamiltonian path $P_1$ joining u and v in $AQ_{n-1}^{0}- \{a, b \}$. Since $a^h, b^h, x, y$ are four distinct vertices in $AQ_{n-1}^1$, by Lemma 5, there exist two disjoint paths $P_2$ and $P_3$ of $AQ_{n-1}^{1}$ such that $P_2$ joins $a^h$ to x, $P_3$ joins $b^h$ to y and $P_2 \cup P_3$ spans $AQ_{n-1}^{1}$. Hence, $C_{\ell }= \langle u, P_1, v, u \rangle$ and $C_{2^n-\ell }=\langle x, y, P_3, b^h, b, a, a^h, P_2, x \rangle$ are the required cycles; see Fig. 5(d) for an illustration.

Subcase 4.4 $\ell = 2^{n-1}-1$.

Obviously, there exists a vertex a in $AQ_{n-1}^{0}- \{u, v \}$ such that $\{ a^h, a^c \} \cap \{x, y \} =\varnothing$. By Lemma 4, there exists a Hamiltonian path $P_1$ joining u and v in $AQ_{n-1}^{0}- \{a \}$. By Lemma 5, there exist two disjoint paths $P_2$ and $P_3$ of $AQ_{n-1}^{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_{n-1}^{1}$. Hence, $C_{\ell }= \langle u, P_1, v, u \rangle$ and $C_{2^n-\ell }=\langle x, y, P_3, a^c, a, a^h, P_2, x \rangle$ are the required cycles; see Fig. 5(e) for an illustration.

Subcase 4.5 $\ell = 2^{n-1}$.

Since both $AQ_{n-1}^0$ and $AQ_{n-1}^1$ are Hamiltonian connected, there exists a Hamiltonian path $P_1$ joining u and v in $AQ_{n-1}^0$, and a Hamiltonian path $P_2$ joining x and y in $AQ_{n-1}^1$. Hence, $C_{\ell }= \langle u, P_1, v, u \rangle$ and $C_{2^n-\ell }=\langle x, P_2, y, x \rangle$ are the required cycles; see Fig. 5(f) for an illustration.

Fig. 5

Illustrations of Case 4 in the proof of Theorem 3.3

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

The vertex u has $2n-3 \geqslant 7$ neighbors in $AQ_{n-1}^{0}$. Since $|\{ x, v^h, v^c, y^h, y^c \}| \leqslant 5$, there exists a vertex $a \in N(u)\cap V(AQ_{n-1}^{0})- \{x \}$ satisfying $\{ a^h, a^c \} \cap \{v, y \} =\varnothing$. Without loss of generality, we assume that $v=u^h$.

Subcase 5.1 $\ell = 4$.

In this subcase, we have $\langle u, a, a^h, v, u \rangle$ is a 4-cycle. By Lemma 4, there exists a Hamiltonian path P joining x and y in $AQ_{n}- \{u, v, a, a^h \}$. Hence, $C_{\ell }= \langle u, a, a^h, v, u \rangle$ and $C_{2^n-\ell }=\langle x, P, y, x \rangle$ are the required cycles; see Fig. 6(a) for an illustration.

Subcase 5.2 $\ell = 5$.

In this subcase, we have $\langle u, v, a^h, a^c, a, u \rangle$ is a 5-cycle. By Lemma 4, there exists a Hamiltonian path P joining x and y in $AQ_{n}- \{u, v, a, a^h, a^c \}$. Hence, $C_{\ell }= \langle u, v, a^h, a^c, a, u \rangle$ and $C_{2^n-\ell }=\langle x, P, y, x \rangle$ are the required cycles; see Fig. 6(b) for an illustration.

Fig. 6

Illustrations of Case 5 in the proof of Theorem 3.3

Subcase 5.3 $6 \leqslant \ell \leqslant 2^{n-2}+2$.

Let $\ell =\ell _1+2$, where $4 \leqslant \ell _1 \leqslant 2^{n-2}$. The vertex x has $2n-3 \geqslant 7$ neighbors in $AQ_{n-1}^{0}$, and $|\{ u, a, v^c, (a^h)^c, y^h, y^c \}- \{x \}| \leqslant 5$. Then, there exists a vertex $b \in N(x) \cap V(AQ_{n-1}^{0})- \{u, a \}$ satisfying $b^h \ne y$. By induction, there exist two vertex-disjoint cycles R and S in $AQ_{n-1}^0$ such that R contains (u, a) with length $\ell _1$, and S contains (b, x) with length $2^{n-1}-\ell _1$. We denote R and S as $\langle u, a, R_1, u \rangle$ and $\langle x, S_1, b, x \rangle$, respectively. By Lemma 4, there exists a Hamiltonian path P joining $b^h$ and y in $AQ_{n-1}^{1}- \{v, a^h \}$. Hence, $C_{\ell }= \langle u, v, a^h, a, R_1, u \rangle$ and $C_{2^n-\ell }=\langle x, y, P, b^h, b, S_1, x \rangle$ are the required cycles; see Fig. 6(c) for an illustration.

Subcase 5.4 $2^{n-2}+3 \leqslant \ell \leqslant 2^{n-1}$.

Let $\ell =\ell _1+\ell _2$, where $4 \leqslant \ell _1 \leqslant 2^{n-2}$ and $2^{n-2}-1 \leqslant \ell _2 \leqslant 2^{n-2}$. There exists a neighbor $b \in N(x) \cap V(AQ_{n-1}^{0})- \{u, a \}$ satisfying $b^h \ne y$. By induction, there exist two vertex-disjoint cycles R and S in $AQ_{n-1}^0$ such that R contains (u, a) with length $\ell _1$, and S contains (b, x) with length $2^{n-1}-\ell _1$. Denote R and S as $\langle u, a, R_1, u \rangle$ and $\langle x, S_1, b, x \rangle$, respectively. There exist two vertex-disjoint cycles $R'$ and $S'$ in $AQ_{n-1}^1$ such that R contains $(v, a^h)$ with length $\ell _2$, and $S'$ contains $(b^h, y)$ with length $2^{n-1}-\ell _2$. We denote $R'$ and $S'$ as $\langle v, R_1', a^h. v \rangle$ and $\langle b^h, S_1', y, b^h \rangle$, respectively. Hence, $C_{\ell }= \langle u, v, R_1', a^h, a, R_1, u \rangle$ and $C_{2^n-\ell }=\langle x, y, S_1', b^h, b, S_1, x \rangle$ are the required cycles; see Fig. 6(d) for an illustration.

This completes the proof of Theorem 1.

Next, we will discuss the two-disjoint-cycle-cover vertex pancyclicity of $AQ_n$.

Lemma 8

The augmented cube $AQ_3$ is two-disjoint-cycle-cover vertex $[3, 4 ]$-pancyclic.

Proof

By Lemma 6, $AQ_3$ is two-disjoint-cycle-cover edge $\{4\}$-pancyclic. Hence, $AQ_3$ is a two-disjoint-cycle-cover vertex $\{4\}$-pancyclic. We only need to prove that for any two distinct vertices $u, v \in V(AQ_3)$, there exist two vertex-disjoint cycles R and S in G such that R contains u with length 3, and S contains v with length 5.

If $\{u, v \} \subseteq V(AQ_{2}^{0})$, we assume that $V(AQ_{2}^{0})=\{u, v, a, b \}$, since $AQ_{2}$ is a complete graph $K_4$, $\langle u, a, b, u \rangle$ is a 3-cycle. And $v^h, v^c \in V(AQ_{2}^{1})$, there exists a Hamiltonian path P joining $v^h$ and $v^c$ in $AQ_{2}^{1}$. Hence, $C_{3}= \langle u, a, b, u \rangle$ and $C_{5}=\langle v, v^h, P, v^c, v \rangle$ are the required cycles.

If $\{u \} \subseteq V(AQ_{2}^{0})$ and $\{v \} \subseteq V(AQ_{2}^{1})$, since v has two neighbors in $AQ_{2}^{0}$, there exists a neighbor a of v in $V(AQ_{2}^{0})-\{u \}$. Without loss of generality, we assume that $v=a^h$, and $V(AQ_{2}^{0})=\{u, a, b, c \}$. Since $AQ_{2}$ is a complete graph $K_4$, $\langle u, b, c, u \rangle$ is a 3-cycle. $v, a^c \in V(AQ_{2}^{1})$, there exists a Hamiltonian path P joining v and $a^c$ in $AQ_{2}^{1}$. Hence, $C_{3}= \langle u, b, c, u \rangle$ and $C_{5}=\langle v, P, a^c, a, a \rangle$ are the required cycles.

This completes the proof of Lemma 8.

Theorem 2

The n-dimensional augmented cube $AQ_{n}$ is two-disjoint-cycle-cover vertex $[3, 2^{n-1} ]$-pancyclic for $n \geqslant 3$.

Proof

The proof will proceed by induction on n. By Lemmas 8, we show that the theorem holds as $n=3$. For $n\geqslant 4$, we assume that $AQ_{n-1}$ is a two-disjoint-cycle-cover vertex $[3, 2^{n-2} ]$-pancyclic by the induction hypothesis. For any two distinct vertices $u, v \in V(AQ_n)$, all possibilities of $\{ u, v \}$ can be divided into the following two cases by symmetry:

Case 1 $\{u, v \} \subseteq V(AQ_{n-1}^{0})$.

Subcase 1.1 $\ell =3$.

By induction, there exist two vertex-disjoint cycles R and S in $AQ_{n-1}^0$ such that R contains u with length 3, and S contains v. By Lemma 4, for every $n \geqslant 4$, $AQ_n$ is the $(2n-3)$-fault-tolerant Hamiltonian, $2n-3\geqslant 5$. Hence, $AQ_n-R$ is still a Hamiltonian. Then, there exists a Hamiltonian cycle in which H contains v in $AQ_n-R$. Hence, $C_{\ell }= R$ and $C_{2^n-\ell }=H$ are the required cycles.

Subcase 1.2 $4 \leqslant \ell \leqslant 2^{n-1}$.

By Theorem 1, $AQ_{n}$ is two-disjoint-cycle-cover edge $[4, 2^{n-1} ]$-pancyclic for $n \geqslant 3$, so $AQ_{n}$ is two-disjoint-cycle-cover vertex $[4, 2^{n-1} ]$-pancyclic.

Case 2 $\{u \} \subseteq V(AQ_{n-1}^{0})$ and $\{v \} \subseteq V(AQ_{n-1}^{1})$.

Subcase 2.1 $\ell =3$.

By induction, there exists a cycle R in $AQ_{n-1}^0$ such that R contains u with length 3. By Lemma 4, $AQ_n-R$ is still a Hamiltonian. Then, there exists a Hamiltonian cycle in which H contains v in $AQ_n-R$. Hence, $C_{\ell }= R$ and $C_{2^n-\ell }=H$ are the required cycles.

Subcase 2.2 $4 \leqslant \ell \leqslant 2^{n-1}$.

By Theorem 1, $AQ_{n}$ is two-disjoint-cycle-cover edge $[4, 2^{n-1} ]$-pancyclic for $n \geqslant 3$, so $AQ_{n}$ is two-disjoint-cycle-cover vertex $[4, 2^{n-1} ]$-pancyclic.

This completes the proof of Theorem 2.

By Theorem 2, we directly obtain the results below.

Theorem 3

The n-dimensional augmented cube $AQ_{n}$ is two-disjoint-cycle-cover $[3, 2^{n-1} ]$-pancyclic for $n \geqslant 3$.

Proof

By Theorem 2, $AQ_{n}$ is two-disjoint-cycle-cover vertex $[3, 2^{n-1} ]$-pancyclic for $n \geqslant 3$, so $AQ_{n}$ is two-disjoint-cycle-cover $[3, 2^{n-1} ]$-pancyclic.

4 Conclusion

In this paper, we consider the problem of two-disjoint-cycle-cover pancyclicity of the n-dimensional augmented cube $AQ_n$. First, we prove that $AQ_n$ is two-disjoint-cycle-cover edge $[4,2^{n-1}]$-pancyclic for $n \geqslant 3$. Next, we further show that $AQ_n$ is two-disjoint cycle cover vertex $[3,2^{n-1}]$-pancyclic for $n \geqslant 3$. Finally, we present a simple proof to verify that $AQ_n$ is two-disjoint-cycle-cover $[3,2^{n-1}]$-pancyclic for $n \geqslant 3$. One possible direction for our future work will be investigating the feasibility of embedding two-disjoint-cycle covers in other network topologies. Furthermore, we are also interested in studying this problem under fault-tolerant conditions.

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.