One of the central issues in evaluating a network is to study the graph embedding problem. In computer network topology design, an important benefit of graph embedding is that we can apply existing algorithms for guest graphs to host graphs. For instance, there is an application of longest path to resolve a practical problem that was encountered in the on-line optimization of a complex flexible manufacturing system (see [5]). This is a good example to show the power of the embedding of paths and cycles in networks. Since vertex and edge faults may develop in computer networks, it is important to consider faulty networks. The main concerns in this regard are fault tolerant routing, fault tolerant path embedding and fault tolerant cycle embedding. Recently, there were many attentions payed on vertex-fault-tolerant $n$-dimensional hypercube $Q_n.$ In [6], it is showed that a fault-free cycle of length at least $2^n-2f$ can be embedded in an $n$-dimensional hypercube when the number $f$ of fault vertices no more than $2n-4$.

The enhanced hypercube $Q_{n,k}(1\leq k \leq n-1)$ is proposed to improve the efficiency of the hypercube structure in [2], since it possesses many properties superior to hypercube [2-4]. The enhanced hypercube is an extension of the hypercube that is constructed by adding some complementary edges. The folded hypercube $FQ_n$ is the special case of the enhanced hypercube $Q_{n,k}$ when $k=1$; see [12, 19, 20].

When investigating a network, the failures often occur, so it is practically meaningful to consider faulty networks. Previous results regarding fault-tolerant cycles or paths embedding on hypercube $Q_n$ or its variant structure as a host graph with only faulty vertices or only faulty edges or both faulty vertices and edges have been proposed. Let $F_v$ and $F_e$ be the set of faulty vertices and faulty edges of $Q_n$. Li et al. [13] proved that every fault-free edge of $Q_n$, for $n\geq 3$, lies on a fault-free cycle of every even length from $4$ to $2^n$ if $|F_e|\leq n-2$. Xu et al. [15] showed that every fault-free edge of $Q_n$, for $n\geq 4$, lies on a fault-free cycle of every even length from $6$ to $2^n$ if $|F_e|\leq n-1$. Tseng [17] showed that a fault-free cycle of length at least $2^n-2|F_v|$ can be embedded on $Q_n$ with $|F_e|\leq n-4$ and $|F_v|+|F_e|\leq n-1$. Sengupta [18] extended the result of Tseng, showing that a fault-free cycle of length $2^n-2|F_v|$ can be embedded on $Q_n$ with $|F_v|>0$ or $|F_e|\leq n-2$, and $|F_v|+|F_e|\leq n-1$. Fu [16] showed that a fault-free cycle of length $2^n-2|F_v|$ can be embedded into $Q_n$ with $|F_v|\leq 2n-4$. Hsieh [21] generalized the result of Fu, proving that $Q_n-F_v-F_e$ contains a fault-free cycle of length $2^n-2|F_v|$ if $|F_e|\leq n-2$ and $|F_e|+|F_v|\leq 2n-4$. Tsai [14] showed that every fault-free edge and fault-free vertex of $Q_n$, for $n\geq 3$, lies on a fault-free cycle of very even length from $4$ to $2^n-2|F_v|$ if $|F_v|\leq n-2$. This paper aims to further explore the vertex-fault-tolerance of $Q_{n,k}$, and discuss its path and cycle embedding. We prove that a fault-free cycle of length at least $2^n-2f$ can be embedded in an $n$-dimensional enhanced hypercube with $|F_v|=f$ vertices, where $n \ge 4$ and $1\le f\le 2n-4.$

The remainder of this paper is organized as follows. Section 2 gives some basic definitions and lemmas used in our discussion. The proofs of our main results are in Section 3. Finally, some concluding remarks are given in Section 4.

For the graph theoretical definitions and notations we follow[1]. A network is usually modeled by a connected graph $G=(V,E)$, where $V$ denotes the set of processors and $E$ denotes the set of communication links between processors. Two graphs $G_1$ and $G_2$ are isomorphic, denoted as $G_1\cong G_2$, if there is a one to one mapping $f$ from $V(G_1)$ onto $V(G_2)$ such that $(u,v)\in E(G_1)$ iff $(f(u),f(v))\in E(G_2)$. Two vertices (nodes) are connected by an edge in a hypercube if their binary labels differ in exactly one bit position. Two distinct edges are adjacent if they are incident with a common vertex. A path is a sequence of adjacent vertices, with the original vertex $v_0$ and end vertex $v_m$, represented as

$$P[v_0,v_m]=[v_0, v_1, v_2, \cdots, v_m],$$

where all the vertices $v_0, v_1, v_2, \cdots, v_m$ are distinct except that possibly the path is a cycle when $v_0=v_m$.

The $n$-dimensional hypercube, denoted by $Q_n$, is a graph with $2^n$ nodes (vertices) $\{x=x_{1}x_2 \cdots x_n:x_i=0$ or $1, 1 \leq i\leq n\}$, and two nodes being adjacent if and only if one coordinate is different. Let $d_{Q_n}(x,y)$ denote the length of the shortest path between vertices $x$ and $y$ in hypercube $Q_n$. Let $x=x_1x_2 \cdots x_n$ and $y=y_1y_2 \cdots y_n $ represent two $n$-bit binary strings respectively. The Hamming distance between $x$ and $y$ is defined as $H(x,y)= \sum\limits_{i=1}^{n}|x_i-y_i|$ which is the number of the different bits between the corresponding strings of two nodes $x$ and $y$. Obviously, by the definition of Hamming distance, we know that $h(x,y)=d_{Q_n}(x,y)$, where $d_{Q_{n}}(x,y)$ is the shortest path between the node $x$ and node $y$ in $Q_{n}$. The Hamming weight of a node $x$ is defined as $hw(x)= \sum\limits_{i=1}^{n}x_i$, so whether a node is even or odd, based on the hamming weight of the node is even or node. In this paper, if we denote the node $u=x_1x_2 \cdots x_{i-1}x_{i}x_{i+1} \cdots x_n$ then $u^{i}=x_1x_2 \cdots x_{i-1}\bar{x}_{i}x_{i+1} \cdots x_n$, for some $i\in \{1,2,\cdots,n\}$, in other words, the binary strings of the two nodes $u$ and $u^{i}$ is different exactly on the $i$th position. And the edge $(u,u^i)$ represents the $i$-dimensional hypercube edge in $Q_n$, $FQ_n$ or $Q_{n,k}$. The set of $i$-dimensional edges is denoted by $E_i=\{(u,u^i)|h(u,u^i)=1, i\in\{1,2, \cdots n\}\}$.

Definition 1 Enhanced hypercube $Q_{n,k}=(V,E)(1 \leq k \leq {n-1})$ is an undirected simple graph. It has the same vertices of $Q_n$, i.e, $V={\{x_1x_2 \cdots x_n:x_i=0 \rm{or} 1, 1 \leq i \leq n\}}$. Two vertices $x=x_1x_2 \cdots x_n$ and $y$ are connected by an edge of $E$ if and only if $y$ satisfies one of the following two conditions:

(1) $y=x_1x_2 \cdots x_{i-1} \bar{x}_{i} x_{i+1}\cdots x_n$, $1 \leq i \leq n$ or

(2) $y=x_1x_2 \cdots x_{k-1} \bar{x}_{k} \bar{x}_{k+1} \cdots \bar{x}_n$.

From the definition of $Q_{n,k}$, the enhanced hypercube $Q_{n,k}$ is the extension of the hypercube by adding the edges $(x_1x_2 \cdots x_n, x_1x_2 \cdots x_{k-1} \bar{x}_{k} \bar{x}_{k+1} \cdots \bar{x}_{n})$, which called complementary edges of enhanced hypercube, denoted by

$$E_c=\{(u,\bar{u})\in E(Q_{n,k})|H(u, \bar{u})=n-k+1\},$$

where $u=x_1x_2 \cdots x_n$, and $\bar{u}=x_1x_2 \cdots x_{k-1} \bar{x}_{k} \bar{x}_{k+1} \cdots \bar{x}_{n}$. As mentioned above, the enhanced hypercube $Q_{n,k}$ contains hypercube $Q_n$ as its subgraph. In addition, the folded hypercube $FQ_{n}$, which is the extension of the hypercube, is regarded as the special case of the enhanced hypercube when $k=1$.

It has showed that $Q_{n,k}$ is $(n+1)$-regular,vertex-transitive and edge-transitive, and have $2^n$ vertices and $(n+1)2^{n-1}$ edges. Due to its good properties, the enhanced hypercube $Q_{n,k}$ have received substantial researches.

Lemma 1 [3] The enhanced hypercube $Q_{n,k}$ can be partitioned into two subgraphs along some component $i(1 \leq i \leq n)$. We use $Q_{n-1,k}^{i0}$ ($Q_{n-1}^{i0}$) and $Q_{n-1,k}^{i1}$ ($Q_{n-1}^{i1}$) to denote the two subgraphs respectively. From the definition of the partition, we can conclude that when $1\le i\le k-1$, $Q_{n-1,k}^{i0}$ and $Q_{n-1,k}^{i1}$ are two $(n-1)$-dimensional enhanced hypercube, that is, $Q_{n,k}=Q_{n-1,k}^{i0}\cup Q_{n-1,k}^{i1}$; when $k\le i \le n$, $Q_{n-1}^{i0}$ and $Q_{n-1}^{i1}$ are two $(n-1)$-dimensional hypercube, that is , $Q_{n,k}=Q_{n-1}^{i0}\cup Q_{n-1}^{i1}$. A vertex $x=x_1x_2 \cdots x_n$ belong to $Q_{n-1,k}^{i0}$($Q_{n-1}^{i0}$) if and only if the $i$th position $x_i=0$; Similarly, $x$ belongs to $Q_{n-1,k}^{i1}$($Q_{n-1}^{i1}$) if and only if the $i$th position $x_i=1$.

Lemma 2 [24] There is an automorphism $\sigma$ of $Q_{n,k}(1\leq k\leq n-1)$, such that $\sigma(E_{i})=E_{j}$ for any $i,$ $j \in \{1,2,\cdots, n,c\}$. Furthermore, we have $Q_{n,k}-E_i$ is isomorphic to $Q_n$(represented as $Q_{n,k}-E_i\cong Q_n$), where $i\in \{k,$ $k+1,$ $k+2,$ $\cdots, n,$ $c\}$.

Lemma 3 [11] For any $x,y\in V(Q_n)$ with $H(x,y),$ there exist paths from $x$ to $y$ with length $l, H(x,y)\le l\le 2^n-1$ and $2|l-H(x,y).$

Lemma 4 [6] There exists a fault-free cycle of length of at least $2^n-2f$ in $Q_n$ with $f$ fault nodes, where $1\le f\le 2n-4$ and $n\ge 3.$

Now let's begin our work. Let $F$ denote the set of fault vertices in $Q_{n,k}$, $f=|F\cap V(Q_{n,k})|$. By Lemma 1, we can partite $Q_{n,k}$ as $Q_{n,k}=Q_{n-1,k}^{i0}\cup Q_{n-1,k}^{i1}$ or $Q_{n,k}=Q_{n-1}^{i0}\cup Q_{n-1}^{i1}$ along different $i$. Therefore we definite

$$f_0=|F\cap V(Q^{i0}_{n-1,k})|, f_1=|F \cap V(Q^{i1}_{n-1,k})|$$

for some $1\le i\le k-1$. And

$$f_0=|F\cap V(Q^{i0}_{n-1})|, f_1=|F \cap V(Q^{i1}_{n-1})|$$

for some $k\le i\le n$. Similarly, in $Q_n$,

$$f=|F\cap V(Q_{n})|, f_0=|F\cap V(Q^{i0}_{n-1})|, f_1=|F \cap V(Q^{i1}_{n-1})|,$$

where $i=1,2,\cdots, n$.

If $x$ is a vertex of graph $G$, denote $N_G(x)=\{u| ux\in E(G)\}$ the neighborhood of $x$.

Since $Q_{11}, Q_{21}$ are trivial, we just discuss $n\ge 3.$

Before considering the cycle embedding in the vertex-fault-tolerant enhanced hypercube, it is worth to point out the similar result for hypercube as follows:

Lemma 5 Let $u,v$ be two fault-free vertices of $Q_{n}$ with $f\le n-1$ fault vertices and $H(u,v)=1$. There exists a fault-free path $P[u,v]$ of length at least $2^n-2f-1$.

Proof We proof the theorem by introduction on $n$. When $n=3$, it is clearly true. Assume that it holds for $n-1(n\ge 4),$ next we consider $n.$ We can partite $Q_n$ along some component $i$ into two $(n-1)$-dimensional subcubes $Q_{n-1}^{i0}$ and $Q_{n-1}^{i1}$.

Case 1 $f_0<f, f_1<f, f=f_0+f_1.$

Since $f_0<f$, by introduction, there exists a fault-free path $P_0[u,v]\in Q_{n-1}^{i0}$ of length at least $2^{n-1}-2f_0-1.$ Select an edge $xy\in P[u,v]$ such that $x^i, y^i \in Q_{n-1}^{i1}$ are fault-free vertices. Since $H(x,y)=1$, we have $H(x^i,y^i)=1$. By introduction, there is a faut-free path $P_1[x^i,y^i]\in Q_{n-1}^{i1}$ of length of at least $2^{n-1}-2f_1-1.$ Then the desired path $P[u,v]$ can be constructed as $(P_0[u,v]-xy)\cup xx^i\cup P_1[x^i,y^i]\cup y^iy$, which is of length at least

$$(2^n-2f_0-1)-1+2+(2^n-2f_1-1)=2^{n}-2f-1,$$

see Figure 1 (a).

Case 2 $f_0=f$ (or, $f_1=f$).

Let $F_v$ be a fault vertex in $Q^{i0}_{n-1}$. Now we can suppose $F_v$ as a fault-free vertex temporarily, by hypothesis, there exists a fault-free path $P_0[u,v]\in Q^{i0}_{n-1}$ of length at least $2^{n-1}-2(f-1)-1,$ which contains no any other $f-1$ faulty vertices. Now we consider whether the vertex $F_v$ is in the path $P_0[u,v]$ or not. Suppose $F_v\in P_0[u,v]$ (otherwise, using the method similarly as Case 1 above, it is easy to discuss), let edges $xF_v, F_vy\in P_0[u,v],$ then $H(x,y)=2$, and $H(x^i,y^i)=2$ obviously. In $Q^{i1}_{n-1}$, using Lemma 3, there exists a fault-free path $P_1[x^i,y^i]\in Q^{i1}_{n-1}$ of length $2^{n-1}-2.$ Therefore, the desired path $P[u,v]$ can be constructed as $(P_0[u,v]-xy)\cup xx^i\cup P_1[x^i,y^i]\cup y^iy$ connecting $u,v$ which is of length at least

$$(2^{n-1}-2(f-1)-1)-2+2+(2^{n-1}-2)=2^{n}-2f-1,$$

see Figure 1 (b).

The proof of the lemma is completed.

Theorem 1 Let $u,v$ be two fault-free vertices of $Q_{n,k}$ with $f\le n-1$ fault vertices and $H(u,v)=1$. There exists a fault-free path $P[u,v]$ of length at least $2^n-2f-1$.

Proof We proof the theorem by introduction on $n$. When $n=3$, it is clearly true. Assume that it holds for $n-1(n\ge 4),$ next we consider $n.$ Without loss of generality, suppose $u,v\in Q_{n-1,k}^{i0}$(or $u,v\in Q_{n-1}^{i0}$), that is $u,v\in E_0.$

Case 1 $f_0<f, f_1<f, f=f_0+f_1.$

We can either execute an $i(1\leq i\le k-1)$-partition on $Q_{n,k}$ to obtain two $(n-1)$-dimensional enhanced hypercubes $Q_{n-1,k}^{i0}$ and $Q_{n-1,k}^{i1}$ or execute an $i(k\le i\le n)$-partition on $Q_{n,k}$ to obtain two $(n-1)$-dimensional hypercubes $Q_{n-1}^{i0}$ and $Q_{n-1}^{i1}$ by Lemma 1. We consider the following subcases:

Case 1.1 $Q_{n,k}=Q_{n-1,k}^{i0}\cup Q_{n-1,k}^{i1}.$

Since $f_0<f$, by introduction, there exists a fault-free path $P_0[u,v]\in Q_{n-1,k}^{i0}$ with length of at least $2^{n-1}-2f_0-1.$ Select an edge $xy\in P[u,v]$ such that $x^i, y^i \in Q_{n-1,k}^{i1}$ are fault-free vertices. Since $H(x,y)=1$, we have $H(x^i,y^i)=1$. By introduction, there is a faut-free path $P_1[x^i,y^i]\in Q_{n-1,k}^{i1}$ of length of at least $2^{n-1}-2f_1-1.$ Then the desired path $P[u,v]$ can be constructed as $(P_0[u,v]-xy)\cup xx^i\cup P_1[x^i,y^i]\cup y^iy$, which is of length at least

$$(2^{n-1}-2f_0-1)-1+2+(2^{n-1}-2f_1-1)=2^{n}-2f-1.$$

Case 1.2 $Q_{n,k}=Q_{n-1}^{i0}\cup Q_{n-1}^{i1}.$

Since $f_0<f\leq n-1\leq 2n-4$ for $n\geq 3$, by Lemma 4, there exists a fault-free path $P_0[u,v]\in Q_{n-1}^{i0}$ with length of at least $2^{n-1}-2f_0-1.$ Select an edge $xy\in P[u,v]$ such that $x^i, y^i \in Q_{n-1}^{i1}$ are fault-free vertices. Since $H(x,y)=1$, we have $H(x^i,y^i)=1$. By Lemma 5, there is a faut-free path $P_1[x^i,y^i])\in Q_{n-1,k}^{i1}$ of length of at least $2^{n-1}-2f_1-1.$ Then the desired path $P[u,v]$ can be constructed as $(P_0[u,v]-xy)\cup xx^i\cup P_1[x^i,y^i]\cup y^iy$, which is of length at least

$$(2^{n-1}-2f_0-1)-1+2+(2^{n-1}-2f_1-1)=2^{n}-2f-1.$$

Case 2 $f_0=f$ (or, $f_1=f$).

Similarly as Case 1, we also consider the partition of enhanced hypercube $Q_{n,k}$, and have the following subcases:

Case 2.1 $Q_{n,k}=Q_{n-1,k}^{i0}\cup Q_{n-1,k}^{i1}.$

Let $F_v$ be a faulty vertex in $Q^{i0}_{n-1,k}$. Now we can suppose $F_v$ as a fault-free vertex temporarily, by hypothesis, there is a path $P_0[u,v]\in Q^{i0}_{n-1}$ of length at least $2^{n-1}-2(f_0-1)-1,$ which contains no any other $f-1$ faulty vertices. Suppose $F_v\in P_0[u,v]$ (otherwise, it is easy to discuss), let edges $xF_v, F_vy\in P_0[u,v],$ then $H(x,y)=2.$ In $Q^{i1}_{n-1}$, $f_1=0$, by Lemma 2, we have $Q^{i0}_{n-1}-E_c \cong Q_{n-1}$. Then using Lemma 3, there exists a fault-free path $P_1[x^i,y^i]\in Q^{i1}_{n-1}$ of length $2^{n-1}-2.$ Therefore, the desired path $P[u,v]$ can be constructed as $(P_0[u,v]-xy)\cup xx_i\cup P_1[x^i,y^i]\cup y^iy$ connecting $u,v$ which is of length at least

$$(2^{n-1}-2(f_0-1)-1)-2+2+(2^{n-1}-2)=2^{n}-2f-1.$$

Case 2.2 $Q_{n,k}=Q_{n-1}^{i0}\cup Q_{n-1}^{i1}.$

Since $f_0=f\leq n-1\leq 2n-4$ for $n\geq 3$, by Lemma 4, there exists a fault-free path $P_0[u,v]\in Q_{n-1}^{i0}$ with length of at least $2^{n-1}-2f_0-1.$ Select an edge $xy\in P[u,v]$ such that $x^i, y^i \in Q_{n-1}^{i1}$ are fault-free vertices. Since $H(x,y)=1$, we have $H(x^i,y^i)=1$. By Lemma 3, there is a faut-free path $P_1[x^i,y^i]\in Q_{n-1}^{i1}$ of length of at least $2^{n-1}-1.$ Then the desired path $P[u,v]$ can be constructed as $(P_0[u,v]-xy)\cup xx^i\cup P_1[x^i,y^i]\cup y^iy$, which is of length at least

$$(2^{n-1}-2f_0-1)-1+2+(2^{n-1}-1)=2^{n}-2f-1.$$

The proof of the theorem is completed.

Lemma 6 Let $u,v$ be two fault-free vertices of $Q_{n}$ with $f\le 2$ fault vertices and $H(u,v)=2$. There exists a fault-free path $P[u,v]$ of length at least $2^n-2f-2$ connecting $u$ and $v.$

Proof We can partite $Q_n$ along some dimension $i=1,2,\cdots ,n$ into two $(n-1)$-dimensional subcubes, that is $Q_n=Q_{n-1}^{i0}\cup Q_{n-1}^{i1}$. We proof the lemma by introduction on $n$. By induction. The lemma holds for $n\ge 3$. Suppose it is true for integer $n-1$, the situation of $n$ can be discussed as follows. Without loss of generality, let $u,v\in Q^{i0}_{n-1}.$ Considering the distribution of faulty vertices, we have the following cases:

Case 1 $f=0.$ By Lemma 3, the lemma is true obviously.

Case 2 $f=1.$

The faulty vertex is in $Q^{i0}_{n-1}.$ By introduction hypothesis,there is a fault-free path $P_0[u,v]\in Q^{i0}_{n-1}$ of length $2^{n-1}-2f-1$ connecting $u,v.$ Select an edge $xy\in P_0[u,v]$ such that $x^i, y^i \in Q^{i1}_{n-1}$ are both fault-free vertices. Lemma 3 indicates there exists a fault-free path $P_1[x^i,y^i]\in Q^{i1}_{n-1}$ between $x^i$ and $y^i$ of length at least $2^{n-1}-1.$ Therefore, the desired fault-free path from $u$ to $v$ can be constructed as $(P_0[u,v]/xy)\cup xx^i\cup P_1[x^i,y^i]\cup y^iy$ of length

$$(2^{n-1}-2f-2)-1+2+(2^{n-1}-1)=2^{n}-2f-2.$$

The faulty vertex is in $Q^{i1}_{n-1}.$ By Lemma 3, there is a fault-free path $P_0[u,v]\in Q^{i0}_{n-1}$ of length at least $2^{n-1}-2.$ Choose an edge $xy\in P_0[u,v],$ using Lemma 5, there exists a fault-free path $P_1[x^i,y^i]\in Q^{i1}_{n-1}$ between $x^i$ and $y^i$ of length at least $2^{n-1}-2f-1.$ Then the desired path $P[u,v]$ can be constructed as $(P_0[u,v]/xy)\cup xx^i\cup P_1[x^i,y^i]\cup y^iy$, which is a path of joining $x, y$ of length at least

$$(2^{n-1}-2)-1+2+(2^{n-1}-2f-1)=2^{n}-2f-2.$$

Caes 3 $f=2.$

Case 3.1.1 $f_0=2$. By hypothesis and Lemma 3, we can easily construct the desired path. We omit it here.

Case 3.1.2 $f_1=2$. The desired path $P[u,v]$ can be obtained using Lemma 3 and Lemma 5. We omit it here.

Case 3.1.3 $f_0=1, f_1=1$. The induction assumption and Lemma 5 guarantee the required path $P[u,v]$. We omit it here.

By considering the above cases, the proof is competed.

Theorem 2 Let $u,v$ be two fault-free vertices of $Q_{n,k}$ with $f\le 2$ fault vertices and $H(u,v)=2$. There exists a fault-free path $P[u,v]$ of length at least $2^n-2f-2$ connecting $u$ and $v.$

Proof By induction. The theorem holds for $n\le 3$. It is easy to clarify the theorem holds under the given conditions. Now we just give a simple example in $Q_{3,1}$ with two faulty vertices. Without loss of generality, we assume the two faulty vertices are $000$ and $001$, and $u=100$, $v=111$, $H(100,111)=2$, we can easily find a fault-free path $P[u,v]=(100,110,111)$, which is of length $2$. Suppose it is true for integer $n-1$, the situation of $n$ can be discussed as follows. Without loss of generality, let $u,v\in Q^{i0}_{n-1,k}$ or $u,v\in Q^{i0}_{n-1}.$

According to the distribution of faulty vertices, we have the following cases:

Case 1 $f=0.$ Lemma 2 indicates $Q_{n,k}-E_c\cong Q_n$. Then the theorem holds because of Lemma 3.

Caes 2 $f=1.$

Case 2.1 $Q_{n,k}=Q_{n-1,k}^{i0}\cup Q_{n-1,k}^{i1}.$

Case 2.1.1 The faulty vertex is in $Q^{i0}_{n-1,k}.$ By the assumption, there is a fault-free path $P_0[u,v]\in Q^{i0}_{n-1,k}$ of length at least $2^{n-1}-2f-2.$ Choose an edge $xy\in P_0[u,v],$ using Lemma 2 and Lemma 3, there exists a fault-free path $P_1[x^i,y^i]\in Q^{i1}_{n-1,k}$ between $x^i$ and $y^i$ of length at least $2^{n-1}-1.$ Then the desired path $P[u,v]$ can be constructed as $(P_0[u,v]/xy)\cup xx^i\cup P_1[x^i,y^i]\cup y^iy$, which is a path of joining $x, y$ of length at least

$$(2^{n-1}-2f-2)-1+2+(2^{n-1}-1)=2^{n}-2f-2.$$

Case 2.1.2 The faulty vertex is in $Q^{i1}_{n-1,k}.$ Lemma 2 and Lemma 3 guarantee a fault-free path $P_0[u,v]\in Q^{i0}_{n-1,k}$ of length $2^{n-1}-2$ connecting $u,v.$ Select an edge $xy\in P_0[u,v]$ such that $x^i, y^i \in Q^{i1}_{n-1,k}$ are both fault-free vertices. Theorem 1 indicates there exists a fault-free path $P_1[x^i,y^i]\in Q^{i1}_{n-1,k}$ between $x^i$ and $y^i$ of length at least $2^{n-1}-2f-1.$ Therefore, the desired fault-free path from $u$ to $v$ can be constructed as $(P_0[u,v]/xy)\cup xx^i\cup P_1[x^i,y^i]\cup y^iy$ of length

$$(2^{n-1}-2)-1+2+(2^{n-1}-2f-1)=2^{n}-2f-2.$$

Case 2.2 $Q_{n,k}=Q_{n-1}^{i0}\cup Q_{n-1}^{i1}.$

Case 2.2.1 The faulty vertex is in $Q^{i0}_{n-1}.$ Lemma 6 indicates that there is a fault-free path $P_0[u,v]\in Q^{i0}_{n-1}$ of length at least $2^{n-1}-2f-2.$ Select an edge $xy\in P_0[u,v],$ using Lemma 3, there exists a fault-free path $P_1[x^i,y^i]\in Q^{i1}_{n-1}$ between $x^i$ and $y^i$ of length at least $2^{n-1}-1.$ Therefore the desired path $P[u,v]$ can be constructed as $(P_0[u,v]/xy)\cup xx^i\cup P_1[x^i,y^i]\cup y^iy$, which is a path of joining $x, y$ of length at least

$$(2^{n-1}-2f-2)-1+2+(2^{n-1}-1)=2^{n}-2f-2.$$

Case 2.2.2 The faulty vertex is in $Q^{i1}_{n-1}.$ Lemma 3 guarantees a fault-free path $P_0[u,v]\in Q^{i0}_{n-1}$ of length $2^{n-1}-2$ connecting $u,v.$ Choose an edge $xy\in P_0[u,v]$ such that $x^i, y^i \in Q^{i1}_{n-1}$ are both fault-free vertices. Lemma 5 indicates there exists a fault-free path $P_1[x^i,y^i]\in Q^{i1}_{n-1}$ between $x^i$ and $y^i$ of length at least $2^{n-1}-2f-1.$ So the desired fault-free path from $u$ to $v$ can be constructed as $(P_0[u,v]/xy)\cup xx^i\cup P_1[x^i,y^i]\cup y^iy$ of length

$$(2^{n-1}-2)-1+2+(2^{n-1}-2f-1)=2^{n}-2f-2.$$

Caes 3 $f=2.$

Case 3.1 $Q_{n,k}=Q_{n-1,k}^{i0}\cup Q_{n-1,k}^{i1}.$

Case 3.1.1 $f_0=2$. By introduction hypothesis, there exists a fault-free path $P_0[u,v]\in Q^{i0}_{n-1,k}$ of length $2^{n-1}-2f-2.$ Select an edge $xy\in P_0[u,v],$ then there is a path $P_1[x^i, y^i]\in Q^{i1}_{n-1,k}$ of length of $2^{n-1}-1$, by Lemma 2 and Lemma 3. Hence, $(P_0[u,v]-xy)\cup xx^i\cup P_1[x^i,y^i]\cup yy^i$, of length at least

$$(2^{n-1}-2f-2)-1+2+(2^{n-1}-1)=2^{n}-2f-2$$

is the desired fault-free path joining $u,v$ (see Figure 2 (a)).

Case 3.1.2 $f_1=2$. Lemma 2 and Lemma 3 indicate there is a path $P_0[u,v]\in Q^{i0}_{n-1,k}$ with length of $2^{n-1}-2$. Select $xy\in P_0[u,v]$ such that $x^i,y^i \in Q^{i1}_{n-1,k}$ are fault-free vertices. By Theorem 1, there exists path $P_1[x^i,y^i]\in Q^{i1}_{n-1,k}$ of length $2^{n-1}-2f-1.$ Then $(P_0[u,v]/xy)\cup xx^i\cup P_1[x^i,y^i]\cup y^iy$ of length at least

$$(2^{n-1}-2)-1+2+(2^{n-1}-2f-1)=2^{n}-2f-2$$

is the required path(see Figure 2 (b)).

Case 3.1.3 $f_0=1, f_1=1$. With assumption, there is a fault-free path $P_0[u,v]\in Q^{i0}_{n-1,k}$ of length $2^{n-1}-2f_0-2.$ Let $x,y\in P_0[u,v]$ and $x^i,y^i\in Q^{i1}_{n-1,k}$ are both fault-free vertices. Theorem 1 guarantees a fault-free path $P_1[x^i,y^i]\in Q^{i1}_{n-1,k}$ of length $2^{n-1}-2f_1-1.$ So the desired path can be constructed as $(P_0[u,v]/xy)\cup xx^i\cup P_1[x^i,y^i]\cup y^iy$ which is of length at least

$$(2^{n-1}-2f_0-2)-1+2+(2^{n-1}-2f_1-1)=2^{n}-2f-2$$

joins $u,v$ (see Figure 2 (c)).

Case 3.2 $Q_{n,k}=Q_{n-1}^{i0}\cup Q_{n-1}^{i1}.$

Case 3.2.1 $f_0=2$. According to Lemma 6 and Lemma 3, we can easily construct the desired path $P[u,v]$ of length at least $2^{n}-2f-2$ similarly as Case 3.1.1 above. We omit it here.

Case 3.2.2 $f_1=2$. Using the similar methods as Case 3.1.2 above, by Lemma 3 and Lemma 5, the desired path connecting $u,v$ can be constructed. We omit it here.

Case 3.2.3 $f_0=1, f_1=1$. By Lemma 6 and Lemma 5, similarly as Case 3.1.3 above, there exists a fault-free path $P[u,v]$ of length at least $2^{n}-2f-2$. We omit it here.

By considering the above cases, the proof is competed.

Lemma 7 Let $u,v\in Q_{n}$ with $f\le 2$ fault vertices and $H(u,v)=3$. There exists a fault-free path $P[u,v]$ of length at least $2^n-2f-1$ between $u$ and $v.$

Proof We use introduction on $n$ to proof this lemma similarly as the proof of Lemma 6, and the desired path $P[u,v]$ can be obtained, we omit it here.

Theorem 3 Let $u,v\in Q_{n,k}$ with $f\le 2$ fault vertices and $H(u,v)=3$. There exists a fault-free path $P[u,v]$ of length at least $2^n-2f-1$ between $u$ and $v.$

Proof We proof the theorem by introduction on $n$.

Case 1 $f=0$. Lemma 2 and Lemma 3 guarantee the theorem true.

Case 2 $f=1.$

By induction, it is true for $n=3$. Assumption it holds for $n-1$ for $n\ge 4$, we consider $n$ as follows. Without loss of generality, let $u,v\in Q^{i0}_{n-1,k}$ or $u,v\in Q^{i0}_{n-1}$.

Case 2.1 $Q_{n,k}=Q_{n-1,k}^{i0}\cup Q_{n-1,k}^{i1}.$

Case 2.1.1 $Q^{i0}_{n-1,k}$ contains the faulty vertex. By the introduction hypothesis, there is a fault-free path $P_0[u,v]\in Q^{i0}_{n-1,k}$ of length $2^{n-1}-2f-1.$ Let $xy\in P_0[u,v],$ with Lemma 2 and Lemma 3, there is a path $P_1[x^i,y^i]\in Q^{i1}_{n-1,k}$ of length $2^{n-1}-1.$ Furthermore a path between $u$ and $v$ can be constructed as $(P_0[u,v]/xy)\cup xx^i\cup P_1[x^i,y^i]\cup y^iy,$ which is of length at least

$$(2^{n-1}-2f-1)-1+2+(2^{n-1}-1)=2^{n}-2f-1.$$

Case 2.1.2 $Q^{i1}_{n-1,k}$ contains the faulty vertex. By Lemma 2 and Lemma 3, there exists a fault-free path $P_0[u,v]$ in $Q^{i0}_{n-1,k}$ of length $2^{n-1}-1.$ Select an edge $xy\in P_0[u,v]$ such that $x^i, y^i \in Q^{i1}_{n-1,k}$ are both fault-free vertices. With Theorem 1, there is a path $P_1[x^i,y^i]\in Q^{i1}_{n-1,k}$ which is of length $2^{n-1}-2f-1$ joining $x^i,y^i.$ Then the desired path $P[u,v]$ can be constructed as $(P_0[u,v]-xy)\cup xx^i\cup P_1[x^i,y^i]\cup y^iy$ which is of length at least

$$(2^{n-1}-1)-1+2+(2^{n-1}-2f-1)=2^{n}-2f-1.$$

Case 2.2 $Q_{n,k}=Q_{n-1}^{i0}\cup Q_{n-1}^{i1}.$

Case 2.2.1 $Q^{i0}_{n-1}$ contains the faulty vertex. Lemma 7 indicates there exists a fault-free path $P_0[u,v]$ of length at least $2^{n-1}-2f-1$. Choose an edge $xy\in P_0[u,v]$ such that $x^i, y^i \in Q^{i1}_{n-1}$ are both fault-free vertices. Using Lemma 3, there is a fault-free path $P_1[x^i,y^i]$ of length $2^{n-1}-1$. Therefore, the desired path $P[u,v]$ can be constructed as $(P_0[u,v]-xy)\cup xx^i\cup P_1[x^i,y^i]\cup y^iy$ which is of length at least

$$(2^{n-1}-2f-1)-1+2+(2^{n-1}-1)=2^{n}-2f-1.$$

Case 2.2.2 $Q^{i1}_{n-1}$ contains the faulty vertex. Lemma 3 guarantees a path $P_0[u,v]$ in $Q^{i0}_{n-1}$ of length $2^{n-1}-1.$ Let $xy\in P_0[u,v],$ with Lemma 5, there is a path $P_1[x^i,y^i]\in Q^{i1}_{n-1}$ of length $2^{n-1}-2f-1.$ Furthermore a path between $u$ and $v$ can be constructed as $(P_0[u,v]/xy)\cup xx^i\cup P_1[x^i,y^i]\cup y^iy,$ which is of length at least

$$(2^{n-1}-1)-1+2+(2^{n-1}-2f-1)=2^{n}-2f-1.$$

Case 3 $f=2.$

Case 3.1 $Q_{n,k}=Q_{n-1,k}^{i0}\cup Q_{n-1,k}^{i1}.$

Case 3.1.1 $f_0=2$. By induction hypothesis, there exists a fault-free path $P_0[u,v]$ in $Q^{i0}_{n-1,k}$ of length at least $2^{n-1}-2f-1.$ Set edge $xy\in P_0[u,v]$, Lemma 2 and Lemma 3 imply a fault-free path $P_1[x^i,y^i]\in Q^{i1}_{n-1,k}$ of length $2^{n-1}-1.$ So the path $(P_0[u,v]/xy)\cup xx^i\cup P_1[x^i,y^i]\cup y^iy$ of length at least

$$(2^{n-1}-2f-1)-1+2+(2^{n-1}-1)=2^{n}-2f-1$$

is the desired path.

Case 3.1.2 $f_0=1$ and $f_1=1$. We can find a fault-free path $P_0[u,v]\in Q^{i0}_{n-1,k}$ with length of $2^{n-1}-2f_0-1$ by introduction hypothesis. Choose an edge $xy\in P_0[u,v]$ such that $x^i,y^i \in Q^{i1}_{n-1,k}$ are both fault-free vertices. Then Theorem 1 means a fault-free path $P_1[x^i,y^i]\in Q^{i1}_{n-1,k}$ of length at least $2^{n-1}-2f_1-1.$ Hence $(P_0[u,v]-xy)\cup xx^i\cup P_1[y,y^i]\cup y^iy$ is a fault-free path of length at least

$$(2^{n-1}-2f_0-1)-1+2+(2^{n-1}-2f_1-1)=2^{n}-2f-1$$

connecting the vertices $u,v.$

Case 3.1.3 $f_1=2$. Lemma 2 and Lemma 3 proposed a fault-free path $P_0[u,v]\in Q^{i0}_{n-1,k}$ of length $2^{n-1}-1.$ Choose an edge $xy\in P_0[u,v]$ such that $x^i,y^i \in Q^{i1}_{n-1,k}$ are both fault-free vertices. Using Theorem 1, a fault-free path $P_1[x^i,y^i]\in Q^{i1}_{n-1,k}$ of length $2^{n-1}-2f-1$ can be found. Then $(P_0[u,v]/xy)\cup xx^i\cup P_1[x^i,y^i]\cup y^iy$ is required, which is of length at least

$$(2^{n-1}-1)-1+2+(2^{n-1}-2f-1)=2^{n}-2f-1.$$

Case 3.2 $Q_{n,k}=Q_{n-1}^{i0}\cup Q_{n-1}^{i1}.$

Case 3.2.1 $f_0=2$. Using the similar methods as Case 3.1.1 above, by Lemma 7 and Lemma 3, the desired path connecting $u,v$ can be constructed. We omit it here.

Case 3.2.2 $f_0=1$ and $f_1=1$. By Lemma 7 and Lemma 5, similarly as Case 3.1.2 aobve, there exists a fault-free path $P[u,v]$ of length at least $2^{n}-2f-1$. We omit it here.

Case 3.2.3 $f_1=2$. According to Lemma 3 and Lemma 5, we can easily construct the desired path $P[u,v]$ of length at least $2^{n}-2f-1$ similarly as Case 3.1.3 above. We omit it here.

By considering the above cases, the proof is competed.

Corollary There exists a fault-free cycle of length at least $2^n-2f$ in $Q_{n,k}\ (n\ge 4)$ with $f$ fault vertices for $1\le f\le 2n-4.$

Proof We proof the theorem by induction on $n.$ When $n=4,$ the theorem is true. Suppose theorem holds for integer $n-1$, Now we consider the situation of $n.$

When $1\le f\le n-2.$

Case 1 $f_0=n-2, f_1=0.$

Case 1.1 $Q_{n,k}=Q_{n-1,k}^{i0}\cup Q_{n-1,k}^{i1}.$

All faulty vertices are in $Q^{i0}_{n-1,k}$, select an edge $uv\in Q^{i0}_{n-1,k},$ using Theorem 1, there exists a fault-free path $P_0[u,v]\in Q^{i0}_{n-1,k}$ of length $2^{n-1}-2f_0-1.$ Since $f_1=0$, by Lemma 2, $Q^{i1}_{n-1,k}-E_c\cong Q_{n-1}$, then by Lemma 3, there is a path $P_1[u^i,v^i]\in Q^{i1}_{n-1,k}$ of length $2^{n-1}-1.$ Therefore, the desired cycle can be constructed as $P_0[u,v]\cup vv^i\cup P_1[v^i,u^i]\cup u^iu$, which is of length

$$(2^{n-1}-2f_0-1)+2+(2^{n-1}-1)=2^{n}-2f.$$

Case 1.2 $Q_{n,k}=Q_{n-1}^{i0}\cup Q_{n-1}^{i1}.$

Since $f_0=n-2\leq 2n-4$ for $n\geq 3$, by Lemma 4, there exists a fault-free cycle $C_0$ of length at least $2^{n-1}-2f_0$ in $Q_{n-1,k}^{i0}$. We can select an edge $uv$ on cycle $C_0$ such that the vertices $u^i,v^i$ are all fault-free vertices. Then in $Q_{n-1}^{i1}$ by Lemma 3, there exists a fault-free path $P_1[u^i,v^i]$ of length at least $2^{n-1}-1.$ Therefore, the desired cycle can be constructed as $(C_0[u,v]-uv)\cup vv^i\cup P_1[v^i,u^i]\cup u^iu$, which is of length

$$(2^{n-1}-2f_0-1)+2+(2^{n-1}-1)=2^{n}-2f.$$

Case 2 $1\le f_0\le n-3, f_1\ge 1.$

Case 2.1 $Q_{n,k}=Q_{n-1,k}^{i0}\cup Q_{n-1,k}^{i1}.$

Select an edge $uv\in Q^{i0}_{n-1,k}$ such that $u,v,u^i,v^i$ are all fault-free vertices. With Theorem 1, there exist fault-free paths $P_0[u,v]\in Q^{i0}_{n-1,k}$ and $P_1(u^1,v^1)\in Q^{i1}_{n-1,k}$ of length at least $2^{n-1}-2f_0-1$ and $2^{n-1}-2f_1-1$ respectively. Then the desired cycle can be constructed as $P_0[u,v]\cup vv^i\cup P_1[v^i,u^i]\cup u^iu$, which is of length

$$(2^{n-1}-2f_0-1)+2+(2^{n-1}-2f_1-1)=2^{n}-2f.$$

Case 2.2 $Q_{n,k}=Q_{n-1}^{i0}\cup Q_{n-1}^{i1}.$

Since $f_0\le n-3\le 2n-4$ for $n\ge 4$, by Lemma 4, there exists a fault-free cycle $C_0$ of length at least $2^{n-1}-2f_0$ in $Q_{n-1}^{i0}$. We can select an edge $uv\in C_0$ such that the vertices $u^i,v^i\in Q_{n-1}^{i1}$ are both fault-free vertices. In $Q_{n-1}^{i1}$, by Lemma 5, there exists a fault-free path $P_1[u^i,v^i]$ of length at least $2^{n-1}-2f_1-1$. Therefore, the desired cycle can be constructed as $(C_0[u,v]-uv)\cup vv^i\cup P_1[v^i,u^i]\cup u^iu$, which is of length

$$(2^{n-1}-2f_0-1)+2+(2^{n-1}-2f_1-1)=2^{n}-2f.$$

When $n-1\le f\le 2n-4$. Without loss of generality, let $Q_{n,k}=Q^{i0}_{n-1}\cup Q^{i1}_{n-1}$ or $Q_{n,k}=Q^{i0}_{n-1,k}\cup Q^{i1}_{n-1,k}$ such that $f_0\ge 1, f_1\ge 1.$

Case 3 $f_0=2n-5, f_1=1$. As the partition of $Q_{n,k}$, we consider the following subcases:

Case 3.1 $Q_{n,k}=Q_{n-1,k}^{i0}\cup Q_{n-1,k}^{i1}.$

Let $F_v\in Q^{i0}_{n-1,k}$ be a faulty vertex. We can suppose $F_v$ as a fault-free vertex temporarily, the $f_0=(2n-5)-1=2n-6$. By introduction hypothesis, there exists a cycle $C_0\in Q^{i0}_{n-1,k}$ of length at least $2^{n-1}-2(f_0-1)$ that contains no any other $f_0-1$ faulty vertices. Considering whether the cycle $C_0$ contains the faulty vertex $F_v$ or not, we have the following subcases:

Case 3.1.1 $F_v\notin C_0.$ Select a section of $C_0$, say $L(u,v)=uwv\in C_0,$ such that $u^i,v^i$ are fault-free and $H(u^i,v^i)=2.$ Then Theorem 2 guarantees a fault-free path $P_1[u^i,v^i]\in Q^{i1}_{n-1,k}$ of length at least $2^{n-1}-2f_1-2.$ Therefore, the desired cycle can be constructed as $(C_0-L(u,v))\cup vv^i\cup P_1[v^i,u^i]\cup u^iu$, which is of length

$$(2^{n-1}-2(f_0-1))-2+2+(2^{n-1}-2f_1-2)=2^{n}-2f,$$

see Figure 3 (a).

Case 3.1.2 $F_v\in C_0.$ Suppose that $L(s,v)=suF_vv$ is a section of $C_0.$ When $u^i, v^i$ are fault-free vertices, the discussion is similar to above. However, if $u^i\in Q^{i1}_{n-1,k}$ is fault vertex, select another neighbor $s$ of $u$ on cycle $C_0,$ this implies $s^i$ is a fault-free vertex in $Q^{i1}_{n-1,k},$ then $H(s^i, v^i)=1$ or $3$. Theorem 1 and Theorem 3 indicate a fault-free path $P_1[s^i,v^i]\in Q^{i1}_{n-1,k}$ of length $2^{n-1}-2f_1-1.$ Then the desired cycle can be constructed as $(C_0-L(s,v))\cup vv^i\cup P_1[v^i,s^i]\cup s^is$ which is of length

$$(2^{n-1}-2(f_0-1))-3+2+(2^{n-1}-2f_1-1)=2^{n}-2f,$$

see Figure 3 (b).

Case 3.2 $Q_{n,k}=Q_{n-1}^{i0}\cup Q_{n-1}^{i1}$

Let $F_v\in Q^{i0}_{n-1}$ be a faulty vertex. We can suppose $F_v$ as a fault-free vertex simultaneously, the $f_0=(2n-5)-1=2n-6$. By Lemma 4, there exists a fault-free cycle $C_0\in Q^{i0}_{n-1}$ of length at least $2^{n-1}-2(f_0-1)$ that contains no any other $f_0-1$ faulty vertices. Considering whether the cycle $C_0$ contains the faulty vertex $F_v$ or not, we have the following subcases:

Case 3.2.1 $F_v\notin C_0.$

Using Lemma 6, with the similar methods of Case 3.1.1 above, we can construct the desired fault-free cycle of length $2^n-2f$. We omit it here.

Case 3.2.2 $F_v\in C_0.$

Using Lemma 5 and Lemma 7, with the similar methods of Case 3.1.2 above, we can construct the desired fault-free cycle of length $2^n-2f$. We omit it here.

Case 4 $n\le f_0\le 2n-6, 1\le f_1\le n-2$

Case 4.1 $Q_{n,k}=Q_{n-1,k}^{i0}\cup Q_{n-1,k}^{i1}$

By assumption, there exists a fault-free cycle $C_0\in Q^{i0}_{n-1,k}$ of length at least $2^{n-1}-2f_0.$ Select an edge $uv\in C_0$ such that $u^i,v^i$ are both fault-free vertices in $Q_{n-1,k}^{i1}$. With Theorem 1, there exists a fault-free path $P_1[u^i,v^i]\in Q^{i1}_{n-1,k}$ of length $2^{n-1}-2f_1-1.$ So the desired cycle can be constructed as $(C_0-uv)\cup uu^i\cup P_1[u^i,v^i]\cup v^iv$ which is of length

$$(2^{n-1}-2f_0)-1+2+(2^{n-1}-2f_1-1)=2^{n}-2f,$$

see Figure 4 (a).

Case 4.2 $Q_{n,k}=Q_{n-1}^{i0}\cup Q_{n-1}^{i1}.$

Using Lemma 4, there is a fault-free cycle $C_0$ of length at least $2^{n-1}-2f_0$ in $Q_{n-1}^{i0}$. Select an edge $uv$ such that $u^i,v^i$ are both fault-free vertices in $Q_{n-1}^{i1}$. Lemma 5 indicates a fault-free path $P_1[u^i,v^i]$ of length at least $2^{n-1}-2f_1-1$ in $Q_{n-1}^{i1}$. So the desired cycle can be constructed as $(C_0-uv)\cup uu^i\cup P_1[u^i,v^i]\cup v^iv$ which is of length

$$(2^{n-1}-2f_0)-1+2+(2^{n-1}-2f_1-1)=2^{n}-2f.$$

Case 5 $1\le f_0\le n-2, 1\le f_1\le n-1.$

Case 5.1 $Q_{n,k}=Q_{n-1,k}^{i0}\cup Q_{n-1,k}^{i1}.$

Let $F_v\in Q^{i1}_{n-1,k}$ be a faulty vertex. We can suppose $F_v$ as a fault-free vertex temporarily, the $f_1=(n-1)-1=n-2$. Using Theorem 1, there exists a cycle $C_1\in Q^{i1}_{n-1,k}$ of length at least $2^{n-1}-2(f_1-1)$ that contains no any other $f_1-1$ faulty vertices. Considering whether the cycle $C_1$ contains the faulty vertex $F_v$ or not, we have the following subcases:

Case 5.1.1 $F_v\notin C_1.$ Select a section of $C_1$, say $L(u,v)=uwv\in C_1,$ such that $u^i,v^i$ are fault-free and $H(u^i,v^i)=2.$ Then Theorem 2 guarantees a fault-free path $P_0[u^i,v^i]\in Q^{i0}_{n-1,k}$ of length at least $2^{n-1}-2f_0-2.$ Therefore, the desired cycle can be constructed as $(C_1-L(u,v))\cup vv^i\cup P_0[v^i,u^i]\cup u^iu$, which is of length

$$(2^{n-1}-2(f_1-1))-2+2+(2^{n-1}-2f_0-2)=2^{n}-2f,$$

see Figure 4 (b).

Case 5.1.2 $F_v\in C_1.$ Suppose that $L(s,v)=suF_vv$ is a section of $C_1.$ When $u^i,v^i$ are fault-free vertices, the discussion is similar to above. However, if $u^i\in Q^{i0}_{n-1,k}$ is fault vertex, select another neighbor $s$ of $u$ on cycle $C_1,$ this implies $s^i$ is a fault-free vertex in $Q^{i0}_{n-1,k},$ then $H(s^i, v^i)=1$ or $3$. Theorem 1 and Theorem 3 indicate a fault-free path $P_0[s^i,v^i]\in Q^{i0}_{n-1,k}$ of length $2^{n-1}-2f_0-1.$ Then the desired cycle can be constructed as $(C_1-L(s,v))\cup vv^i\cup P_0[v^i,s^i]\cup s^is$ which is of length

$$(2^{n-1}-2(f_1-1))-3+2+(2^{n-1}-2f_0-1)=2^{n}-2f,$$

see Figure 4 (c).

Case 5.2 $Q_{n,k}=Q_{n-1}^{i0}\cup Q_{n-1}^{i1}.$

Let $F_v\in Q^{i1}_{n-1}$ be a faulty vertex. We can suppose $F_v$ as a fault-free vertex temporarily, the $f_1=(n-1)-1=n-2$. Lemma 4 indicates that there exists a fault-free cycle $C_1\in Q^{i1}_{n-1}$ of length at least $2^{n-1}-2(f_1-1)$ that contains no any other $f_1-1$ faulty vertices. Considering whether the cycle $C_1$ contains the faulty vertex $F_v$ or not, we have the following subcases:

Case 5.2.1 $F_v\notin C_1$

Using Lemma 6, with the similar methods of Case 5.1.1 above, we can construct the desired fault-free cycle of length $2^n-2f$. We omit it here.

Case 5.2.2 $F_v\in C_1$

According to Lemma 5 and Lemma 7, we can easily construct the desired cycle of length at least $2^{n}-2f$ similarly as Case 5.1.2 above. We omit it here.

By considering the above cases, the proof is competed.

Network topology is an important issue in the design of computer networks since it is crucial to many key properties such as the efficiency and fault tolerance. When investigating a network, every component in the network may have the different reliability, so it is important to consider the properties of networks with vertex-faults and edge-faults. In this article, we focus on the fault-tolerant paths and cycles embedding on the $n$-dimensional enhanced hypercube $Q_{n,k} (1 \leq k \leq n-1)$, which is an important network topology for parallel processing computer systems. Based on the investigated properties of vertex-fault-tolerant properties, in the hypercube and the folded hypercube, we further concentrate on the paths and cycles embedding on the enhanced hypercube $Q_{n,k} (1 \leq k \leq n-1)$ with the faulty vertex set $F_v$ and faulty edges set $F_e$. We showed that a fault-free cycle of length at least $2^n-2f$ can be embedded in $n$-dimensional enhanced hypercube with $|F_v|=f$ vertices, where $n \ge 3$ and $1\le f\le 2n-4.$

When investigating the embedding problem, we modeled it as a guest graph $G_1$ into a host graph $G_2$, which is a one-to-one mapping from the vertex set of $G_1$ into the vertex set of $G_2$. The embedding structure, such as linear arrays and rings, are suitable for designing simple algorithms with low communication costs. A large amount of efficient algorithms designed on the two fundamental networks for parallel and distributed computation to solve algebraic problems and graph problems can be found in previous works [20, 22]. These applications motivate us to study the cycle embedding on networks. Based on the construction in the proof, it's not difficult to design an efficient recursive algorithm to construct as large as possible cycles on the vertex-fault-tolerant enhanced hypercube. And we can conclude that our algorithms design executed on vertex-fault-tolerant enhanced hypercube are extremely efficient and robust.

Routing (path) is a process of transmitting messages among processors, and it is suitable for designing simple algorithms with low communication costs. The efficiency and reliability are based on the path, because they can be used to accelerate the transmission rate, avoid congestion, and provide alternative communication routs. In addition, the routing (path) also plays great importance on parallel and distributed computing. Based on these applications, we can conclude that our algorithms design executed on edge-fault-tolerant enhanced hypercube are extremely efficient and robust.

Edge and vertex failures may occur simultaneously when investigating the networks, which motivate us to research on the fault-free cycle embedding on enhanced hypercube $Q_{n,k}$ with both edge and vertex failures. Consequently, the next step of our investigation can be concentrated on how many faulty edges and faulty vertices can be tolerant simultaneously such that $Q_{n,k}$ is fault-free bipancyclic or has as many as possible fault-free odd cycles.