Hypercube is one of the most popular interconnection networks discovered for parallel computation. The hypercube which is denoted by $Q_n$ is an undirected graph with $2^n$ vertices (nodes) each labeled with a distinct binary string. Two vertices are connected by an edge if and only if their labels differ in one bit. The hypercube possesses many beautiful properties, such as regular structure, small diameter, and good connection (see [1-3]), all of which are very important for designing parallel systems. As the importance of hypercubes, many variants of $Q_n$ have been proposed, among which, for instance, are crossed hypercube, argument hypercube, folded hypercube and enhanced hypercube.

As an enhancement on the hypercube $Q_n$, the enhanced hypercube $Q_{n, k}$ proposed by Tzeng and Wei (see [4]), not only retains some of the favorable properties of $Q_n$, but also improves the efficiency of the hypercube structure, since it possesses many properties superior to hypercube (see [5-7]). For example, the diameter of the enhanced hypercube is almost half of the hypercube. The hypercube is $n$-regular and $n$-connected, whereas the enhanced hypercube is $(n+1)$-regular and $(n+1)$-connected. The complete binary trees can not be embedded in the hypercube, while complete binary trees can be embedded in the enhanced hypercubes under some restricted condition (see [6]). Its special case of $k = 1$ is the well-known folded hypercube (denoted by $FQ_{n}$) which has received substantial researches (see [6, 8-10]).

The graph embedding problem is a central issue in evaluating a network. The embedding of one guest graph $G$ into another host graph $H$ can be defined as a one-to-one mapping $f$ from the vertex set of $G$ to the vertex set of $H$ [11]. An edge of $G$ corresponds to a path of $H$ under the mapping $f$. Cycles and paths, which are a kind of fundamental topology for parallel and distributed computing, are suitable for local area networks and for the designing simple algorithms with low communication cost. Because these architectures are extensively applied in parallel systems, it is crucial to consider the embedding of efficient paths and cycles in networks.

Because edges (links) or vertices (nodes) in a network may fail accidentally, it is practically meaningful to consider faulty networks. Hence, a number of fault-tolerant embedding options for specific topologies were discussed in researches (see [12-29]). Among them, fault-tolerant cycles and paths embedding in hypercubes have received a great deal of attention in recent years. For example, let $F_v$ be the set of faulty vertices of $Q_n$. Yang et al. [13] showed that a fault-free cycle of length of at least $2^{n}-2f_{v}$ can be embedded in $Q_{n}$ with $1\leq f_{v}\leq n-2$. Fu [14] showed that a fault-free cycle of length of at least $2^{n}-2f_{v}$ can be embedded in $Q_{n}$ with $ f_{v}\leq 2n-4$. Du and Xu [15] extended the result of Fu, proving that $Q_n$ contains a fault-free even cycle of length $2^n-2f_{v}$ if $f_{v}=2n-3$ and $n \geq 5$. Fu [16] also proved that a fault-free path of length at least $2^{n}-2f-1$ (or $2^{n}-2f-2$) can be embedded in $Q_{n}$$(n\geq 3)$ between two arbitrary nodes of odd (or even) distance with $f_{v}\leq n-2$. Furthermore, Kueng et al. [17] refer the conditional fault model, which assumes that each nodes is incident to at least two fault-free nodes, showed that in any hypercube $Q_n(n\geq 3)$, there exists a path of length at least $2^{n}-2f-1$ (respectively, $2^{n}-2f-2$) between any two nodes of odd (respectively, even) distance if it has up to $(2n-6)$ faulty vertices. All the above research is the issue on cycles or paths embedding on faulty $Q_n$, the objective of this paper is to further extend the research of these unknown features, particularly those important features already known to $Q_n$, but unknown to $Q_{n, k}$.

The rest of this paper is organized as follows. In Section 2, some basic definitions and lemmas used in our discussion are proposed. In Section 3, our main results are proved. We mainly discuss the embedding of paths and cycles. When $|F_{v}|=f_v\leq n-1$, using an mathematical inductive method, we showed that $Q_{n, k}-F_v$ contains a fault-free path of length of at least $2^{n}-2f_{v}-1$ between any two nodes of odd distance. Furthermore, when $1\leq|F_{v}|=f_v\leq 2n-3$, if $n$ and $k$ have the same parity, there exits a fault-free cycle of even length at least $2^n-2f_v$, where $n\geq 4$. If $n$ and $k$ have different parity, there exists a fault-free cycle, which is of even length of at least $2^n-2f_v$ in $Q_{n, k}-F_v$, where $n\geq 4$; and simultaneously, there exists a fault-free cycle, which is of odd length of at least $2^n-2f_v+1$ in $Q_{n, k}-F_v$, where $n\geq 3$. Finally, some concluding remarks are given in Section 4.

For the graph theoretical definitions and notations we follow [3]. A network is usually modeled by a connected graph $G=(V, E)$, where $V(G)$ and $E(G)$ represent the vertex and edge sets of $G=(V, E)$ respectively. Two nodes $x$ and $y$ of $G$ are adjacent if $(u, v)\in E(G)$. For a node $u$ of $G$, its neighborhood $N_{G}(u)$ is defined by $N_{G}(u)= \{v \in V (G) | (u, v) \in E(G)\}$. $G$ is bipartite if $V$ can be partitioned into two subsets $V_1$ and $V_2$, such that every edge in $G$ joins a vertex of $V_1$ with a vertex in $V_2$. Then the bipartite graph can be denoted as $G=(V_{1}\cup V_{2}, E)$, where $\{V_{1}\cap V_{2}\}=\phi$, and $E\subseteq \{(x, y), x\in V_{1}, y\in V_{2}\}$. We say that $V_1$ and $V_2$ are bipartite sets of $G$, and $V_{1}\cup V_{2}$ is a bipartite. A bipartite graph is bipancyclic if it contains a cycle of every even length from $4$ to $|V(G)|$. A graph is said to be pancyclic if it contains a cycle of every length from $3$ to $|V(G)|$. 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)$ to $V(G_2)$ such that $(u, v)\in E(G_1)$ if and only if $(f(u), f(v))\in E(G_2)$.

A path $P$ of length $m$ from a node $x$ to a node $y$ in a graph $G$ is a sequence of adjacent vertices $(v_0, v_1, v_2, \dots, v_m)$, with the original vertex $x=v_0$ and end vertex $y=v_m$. For convenience, we write $P(x, y)$ as $P(v_0, v_m)=(v_0, v_1, v_2, \dots, v_m)$ where all the vertices $v_0, v_1, v_2, \dots, v_m$ are distinct except that possibly the path is a cycle when $v_0=v_m$. Two paths are vertex-disjoint if and only if they do not have any vertices in common. A cycle is called a Hamiltonian cycle if it traverses every vertex of $G$ exactly once. A cycle of length $k$ is called a $k$-cycle; a $k$-cycle is odd or even depending on whether $k$ is odd or even. A cycle is fault-free if it contains neither a faulty vertex nor a faulty edge.

An $n$-dimensional hypercube $Q_n$ is an undirected graph with $2^n$ vertices(nodes), and the hypercube $Q_{n}$ has vertex set $V(Q_{n})={\{x_1x_2 \cdots x_n:x_i=0 \rm{or} 1, 1 \leq i \leq n\}}$, with two vertices $x_{1}x_{2}\cdots x_{n}$ and $y_{1}y_{2}\cdots y_{n}$ being adjacent if and only if they differ in exactly one bit. Let $x$ and $y$ be two vertices of hypercube $Q_n$, $d_{Q_n}(x, y)$ denote the length of the shortest path between $x$ and $y$ in hypercube $Q_n$. The Hamming distance between $x$ and $y$, denoted by $h(x, y)$, is the number of different bits between the corresponding strings of $x$ and $y$, that is, the length of the distance of the shortest path between the $x$ and $y$ in $Q_n$. 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 $x$ and $y$ in $Q_{n}$. The Hamming weight of a vertex $x$ is defined as $hw(x)= \sum\limits_{i=1}^{n}x_i$, so whether a vertex is even or odd, based on the hamming weight of the vertex is even or odd. It is well known $Q_n$ that is a bipartite graph with partite sets $V_{0}(Q_n) = \{ x\in V (Q_n) | hw(x) \rm{is even} \}$ and $V_{1}(Q_n)=\{y\in V (Q_n) | hw(y) \rm{is odd} \}$. It is also known that $Q_n$ is vertex-transitive and edge-transitive.

By the definition, for a given $1\leq i\leq n$, we can partition $Q_n$ into two $(n-1)$-cubes $Q_{n-1}^{i0}$ and $Q_{n-1}^{i1}$ along some $i$ such that $Q_n=Q_{n-1}^{i0}\cup Q_{n-1}^{i1}$. A vertex $x_{1}x_{2}\cdots x_{n}\in V(Q_{n-1}^{i0})$ if and only the $i$th position $x_{i}=0$; Similarly $x_{1}x_{2}\cdots x_{n}\in V(Q_{n-1}^{i1})$ if and only the $i$th position $x_{i}=1$. Obviously, $Q_{n-1}^{i0}$ and $Q_{n-1}^{i1}$ are isomorphic to $Q_{n-1}$.

An $n$-dimensional enhanced hypercube $Q_{n, k}$ is obtained by adding some complementary edges from hypercube $Q_n$, and it can be defined as follows:

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 adjacent if $y$ satisfies one of the following two conditions:

(1) $y=x_1x_2\cdots x_{i-1}\bar{x}_ix_{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$.

According to the above definition, it can be easily shown that $Q_{n, k}$ contains $Q_n$ as its subgraph. We can also get that $n$-dimensional enhanced hypercube $Q_{n, k}$ has $2^{n-1}$ more edges than $n$-dimensional hypercube $Q_n$. It has been showed that the enhanced hypercube is $(n+1)$-regular and has $2^n$ vertices and $(n+1)2^{n-1}$ edges. We call the edges of hypercube are hypercube edges and use $E_h$ to denote them, the other $2^{n-1}$ edges are complementary edges and use $E_c$ to denote them. For convenience, we can use $\bar{x}$ to denote the vertex $\bar{x}_1\bar{x}_{2}\cdots \bar{x}_n$. Obviously, $x\bar{x}$ is an complementary edge. Since $Q_{n, k}$ contains $Q_{n}$ as its subgraph, then $Q_{n, k}-E_c\cong Q_n$.

Lemma 1 (see [5])$Q_{n, k}$ can be partitioned into two subgraphs along some components $i(1\leq i\leq n)$. We use $Q_{n-1, k}^{i0}$ and $Q_{n-1, k}^{i1}$ to denote the two parts respectively. A vertex $x=x_1x_2\cdots x_n$ belong to $Q_{n-1, k}^{i0}$ if and only if the $i$th position $x_i=0$; Similarly, $x\in Q_{n-1, k}^{i1}$ if and only if the $i$th position $x_i=1$. When $i<k$, $Q_{n-1, k}^{i0}$ and $Q_{n-1, k}^{i1}$ are two $(n-1)$-dimensional enhanced hypercube; When $i\geq k$, $Q_{n-1, k}^{i0}$ and $Q_{n-1, k}^{i1}$ are two $(n-1)$-dimensional hypercube.

Lemma 2  (see [26]) Let $x$ and $y$ be two distinct vertices in an $n$-cube and $h(x, y)=d$, where $n\geq 1$. There are paths $P(u, v)$ in the $n$-cube whose length are $d, $ $d+2, $ $d+4, \cdots, c, $ where $c=2^n-1$ if $d$ is odd, and $c=2^n-2$ if $d$ is even.

Lemma 3  (see [18]) Let $x$ and $y$ be two distinct vertices of an $n$-dimensional cube. Then, there exists a partition which can partite the $n$-cube into two $(n-1)$-dimensional subcubes such that $x\in V(Q_{n-1}^{0})$ and $y\in V(Q_{n-1}^{1})$.

Lemma 4  (see [14]) There exist a fault-free cycle of length of at least $2^{n}-2f_{v}$ in $Q_{n}$ with $f$ faulty vertices, where $1\leq f_{v}\leq 2n-4$ and $n\geq4 $.

Lemma 5   (see [15]) In $Q_{n}$, if $n\geq5 $, $f_{v}=2n-3$, then there exists a fault-free even cycle of length at least $2^{n}-2f_{v}$.

Lemma 6   (see [14]) Let $e_{1}$ and $e_{2}$ be two distinct edges in $Q_{n}$ with $f_{v}\leq 1$ fault vertices, where $n\geq 3$. Suppose $e_{1}$ connects vertices $x$ and $y$. There exists a fault-free path $P(x, y)$ of length of at least $2^{n}-2f_{v}-1$ in $Q_{n}$ that contains edge $e_{2}$.

Lemma 7   (see [16]) Let $x$ and $y$ be two distinct vertices in $Q_{n}$ with $f_{v}\leq n-2$ fault vertices, where $n\geq 3$. If $h(x, y)$ is even, then there exists a fault-free path $P(x, y)$ of length at least $2^{n}-2f_{v}-2$.

In this section, for a faulty set $F=F_{v}\cup F_{e}$, let $f_{v}=|F_v|$ and $f_{e}=|F_e|$, where $F_{v}\subset V(Q_{n})$ and $F_{e}\subset V(Q_{n})$. For any $i\in \{1, 2, \cdots, n\}$, we always express $Q_{n}=Q_{n-1}^{i0}\cup Q_{n-1}^{i1}$, let $F_{0}=F_{v}\cap Q_{n-1}^{i0}$ and $F_{1}=F_{v}\cap Q_{n-1}^{i1}$. Let $f_{0}=|F_0|$ and $f_{1}=|F_1|$.

Lemma 8   Let $Q_n$ have exactly one faulty vertex $f\in X$. For any two fault-free adjacent vertices $u$ and $v$ of $Q_n$, where $n\geq 3$, there exist fault-free paths connecting $u$ and $v$ in $Q_n$ whose length are from $1$ to $2^n-3.$

Proof  We prove this lemma by induction on $n\geq 3$. For $n=3$. we need to construct a path of every odd length from $1$ to $5$ between any two distinct adjacent vertices $u$ and $v$ in $Q_3-f$. Since $Q_3$ is vertex-symmetric, without loss of generality, we may assume that the fault vertices is $f=000$ and the two adjacent vertices are $u=001$ and $v=101$, then a fault-free path of 1, 3 and 5 are constructed as follows: (001, 101), (001, 011, 111, 101) and (001, 011, 010, 110, 111, 101). In the following, we consider the situation $n\geq 4$. Since $u$ and $v$ are two adjacent vertices, $Q_{n}$ can be partitioned into two $(n-1)$-dimensional subcube $Q_{n-1}^{i0}$ and $Q_{n-1}^{i1}$ along some dimension $i$ $(1\leq i\leq n)$ such that $u$ and $v$ be in the same subgraph. Without loss of generality, we assume $f\in Q_{n-1}^{i0}$. Then we have the following cases:

Case 1  $u, v\in V(Q_{n-1}^{i0})$. In $Q_{n-1}^{i0}$, by the induction hypothesis, there exist paths connecting $u$ and $v$, whose length are from $1$ to $2^{n-1}-3$. In the following, we construct a path of every odd length from $2^{n-1}-1$ to $2^n-3$ between $u$ and $v$. Since the longest path $P_0(u, v)$ is of length $2^{n-1}-3$, we can select two adjacent nodes $x$ and $y$ from the longest path $P_0(u, v)$, such that $P_0(u, v)=P_{0}(u, x)\cup (x, y)\cup P_{0}(y, u)$, $\{x, y\}\cap \{f\}=\emptyset $ and $\{x^{i}, y^{i}\}\in V(Q_{n-1}^{i1})$. Obviously, since $h(x^{i}, y^{i})=1$, by lemma 2, then in $Q_{n-1}^{i0}$, there exists a fault-free path $P_1(x^{i}, y^{i})$ connecting the nodes $x^{i}$ and $y^{i}$, whose length is from $1$ to $2^{n-1}-1$. The desired path $P(u, v)$ can be constructed as $P_0(u, x)\cup (x, x^{i})\cup P_1(x^{i}, y^{i})\cup (y^{i}, y)\cup P_0(y^{i}, v)$, whose length is from from $2^{n-1}-1$ to $2^n-3$ (refer to Fig. 1. (a)) (in this paper, all of the symbols $\cup $ are represent the path-conjunction operations, which are used to connecting the paths or edges).

Case 2  $u, v\in V(Q_{n-1}^{i1})$. In $Q_{n-1}^{i1}$, $h(u, v)=1$, by Lemma 2, $Q_{n-1}^{i1}$ contain paths of every odd length from $1$ to $2^{n-1}-1$ between $u$ and $v$. We next construct paths connecting $u$ and $v$ of every odd length from $2^{n-1}+1$ to $2^n-3$. Let $P_1(u, v)$ be the longest path $P_0(u, v)$ of length $2^{n-1}-1$ in $Q_{n-1}^{i1}$, we select an edge $(x^{i}, y^{i})$ in the longest path $P_1(u, v)$, such that $P_1(u, v)=P_{1}(u, x^{i})\cup (x^{i}, y^{i})\cup P_{1}(y^{i}, v)$, $\{x, y\}\in V(Q_{n-1}^{i0})$ and $\{x, y\}\cap \{f\}=\emptyset $.(If such vertex $x$ and $y$ do not exist, we have $|F_v|\geq 2$, which is a contradiction.) In $Q_{n-1}^{i0}$, since $h(x, y)=1$, $f\in V(Q_{n-1}^{i0})$, by induction hypothesis, there exists a fault-free path $P_0(x, y)$ with length $1, $ $3, $ $5, \cdots, 2^{n-1}-3$ inclusive. The desired path $P(u, v)$ can be constructed as $P_1(u, x^{i})\cup (x^{i}, x)\cup P_0(x, y)\cup (y, y^{i})\cup P_{1}(y^{i}, v)$, whose length is $2^{n-1}+1$ to $2^n-3$ (refer to Fig. 1 (b)).

By analyzing the above cases, the proof of the lemma is completed.

Lemma 9   Suppose that $Q_n$ have two faulty vertex $f_{1}$ and $f_{2}$, where $n\geq 3$. For any two fault-free distinct adjacent vertices $u$ and $v$, there exists a fault-free path of every odd length from 1 to $2^{n}-5$.

Proof  We show this lemma by induction on $n\geq 3$. For $n=3$, we can construct a path which satisfies our theorem. Since $Q_3$ is vertex-symmetric, we may assume that the two adjacent vertices are $u=000$ and $v=010$. When the two faulty vertex are adjacent, because of the symmetric of $Q_3$, let $f_{1}=101$ and $f_{2}=111$, then a fault-free path of 1 and 3 are constructed as follows: (000, 010) and (000, 001, 011, 010). When the two faulty vertex are not adjacent, because of the symmetric of $Q_3$, let $f_{1}=101$ and $f_{2}=011$, then a fault-free path of 1 and 3 are constructed as follows: (000, 010) and (000, 100, 110, 010). In the following, we consider the situation $n\geq 4$. Since $u$ and $v$ are two adjacent vertices, we can partite $Q_{n}$ into two $(n-1)$-dimensional hypercube $Q_{n-1}^{i0}$ and $Q_{n-1}^{i1}$ along some dimension $i$$(1\leq i\leq n)$ such that $u$ and $v$ be in the same subgraph $Q_{n-1}^{i0}$. We will consider the following cases:

Case 1  $f_{1}$ and $f_{2}$ be in the same subgraph.

Case 1.1  $f_{1}$, $f_{2}\in V(Q_{n-1}^{i0})$. In $Q_{n-1}^{i0}-F_{v}$, by the induction hypothesis, there exist fault-free paths of every odd length from 1 to $2^{n-1}-5$ between $u$ and $v$. In the following, we construct a path of every odd length from $2^{n-1}-3$ to $2^n-5$ between $u$ and $v$. Let $P_{0}(u, v)$ be a path of length $2^{n-1}-5$ joining $u$ and $v$ in $Q_{n-1}^{i0}-F_{v}$, we select an edge $(s, r)$ on path $P_{0}(u, v)$ such that $\{s^{i}$, $r^{i}\}\in V(Q_{n-1}^{i1})$, it is easy to know $h(s^{i}, r^{i})=1$, by Lemma 2, there exists a path $P_{1}(s^{i}, r^{i})$ of every odd length from 1 to $2^{n-1}-1$ between $s^{i}$ and $r^{i}$. Then the desired path $P(u, v)$ can be constructed as $P_0(u, s)\cup (s, s^i)\cup P_1(s^i, r^i)\cup (r^i, r)\cup P_0(r, v)$, whose length is from $2^{n-1}-3$ to $2^n-5$ (refer to Fig. 2 (a)).

Case 1.2   $f_{1}$, $f_{2}\in V(Q_{n-1}^{i1})$. In $Q_{n-1}^{i0}$, $h(u, v)=1$, by Lemma 2, there exist paths every odd length from 1 to $2^{n-1}-1$ between $u$ and $v$. We next construct a path of every odd length from $2^{n-1}+1$ to $2^n-5$ between $u$ and $v$. Let $P_{0}(u, v)$ be a path of length $2^{n-1}-1$ joining $u$ and $v$ in $Q_{n-1}^{i0}$, we select an edge $(s, r)$ on path $P_{0}(u, v)$ such that $\{s^{i}$, $r^{i}\}\in V(Q_{n-1}^{i1})$ and $\{s^{i}, r^{i}\}\cap\{ f_{1}, f_{2}\}=\phi$. In $Q_{n-1}^{i1}-F_{v}$, by the induction hypothesis, there exists a fault-free path of every odd length from 1 to $2^{n-1}-5$ between $s^{i}$ and $r^{i}$. Then the desired path $P(u, v)$ can be constructed as $P_0(u, s)\cup (s, s^i)\cup P_1(s^i, r^i)\cup (r^i, r)\cup P_0(r, v)$, whose length is from $2^{n-1}+1$ to $2^n-5$ (refer to Fig. 2 (b)).

Case 2  $f_{1}$ and $f_{2}$ be in the different subgraph. Without loss of generality, let $f_{1}\in V(Q_{n-1}^{i0})$, $f_{2}\in V(Q_{n-1}^{i1})$ (the discussion of $f_{1}\in V(Q_{n-1}^{i1})$, $f_{2}\in V(Q_{n-1}^{i0})$ is similar to this case.) In $Q_{n-1}^{i0}-f_{1}$, $h(u, v)=1$, by Lemma 8, there exists a fault-free path of every odd length from 1 to $2^{n-1}-3$ between $u$ and $v$. In the following, we construct a path of every odd length from $2^{n-1}-1$ to $2^n-5$ between $u$ and $v$. Let $P_{0}(u, v)$ be a path of length $2^{n-1}-3$ joining $u$ and $v$ in $Q_{n-1}^{i0}-f_{1}$, we select an edge $(s, r)$ on path $P_{0}(u, v)$ such that $\{s^{i}$, $r^{i}\}\in V(Q_{n-1}^{i1})$ and $\{s^{i}, r^{i}\}\cap f_{2}=\phi$, it is easy to know $h(s^{i}, r^{i})=1$. In $Q_{n-1}^{i1}-f_{2}$, $h(s^{i}, r^{i})=1$, by Lemma 8, there exists a fault-free path of every odd length from 1 to $2^{n-1}-3$ between $s^{i}$ and $r^{i}$. Then the desired path $P(u, v)$ can be constructed as $P_0(u, s)\cup (s, s^i)\cup P_1(s^i, r^i)\cup (r^i, r)\cup P_0(r, v)$, whose length is from $2^{n-1}-1$ to $2^n-5$ (refer to Fig. 2 (c)).

Theorem 1   Let $x$ and $y$ be two arbitrary fault-free vertices of enhanced hypercube $Q_{n, k}$$(n\geq 3, 1\leq k\leq n-1)$ with $|F_{v}|=f_{v}\leq n-1$. There exists a fault-free path $P(x, y)$ of length of at least $2^{n}-2f_{v}-1$ in $Q_{n, k}-F_v$ when $h(x, y)$ is odd.

Proof  We show this lemma by induction on $n\geq 3$. For $n=3$, $|F_{v}|=2$, now we consider $Q_{3, 1}$ and $Q_{3, 2}$. Since $h(x, y)$ is odd, it is easy to know that $h(x, y)=1$ or $h(x, y)=3$ in $Q_{3, 1}$ and $Q_{3, 2}$. Since $Q_3$ is vertex-symmetric, we may assume that $x=010$ and $y=110$ or $x=010$ and $y=101$. In $Q_{3, 1}$, we consider two subcases. If the two faulty vertex are adjacent, because of the symmetric of $Q_3$, let $f_{1}=000$ and $f_{2}=001$, then a fault-free path of 3 are constructed as follows: (010, 011, 111, 110) and (010, 110, 111, 101). If the two faulty vertex are not adjacent, because of the symmetric of $Q_3$, let $f_{1}=000$ and $f_{2}=011$, then a fault-free path of 3 are constructed as follows: (010, 101, 111, 110) and (010, 110, 111, 101). In the following, we will consider $n\geq 4$.

Let $w$ and $z$ are two distinct faulty vertices. Applying Lemma 1 and Lemma 3, $Q_{n, k}$ can be partitioned into two $(n-1)$-dimensional enhanced hypercube $Q_{n-1, k}^{i0}$ and $ Q_{n-1, k}^{i1}$ along some component $i(1 \leq i \leq k)$ such that one contains the vertex $w$ and the other contains the vertex $z$. In the following, for a faulty vertex set $F_{v}$, let $f_{v}=|F_v|$, $F_{0}=F_{v}\cap V(Q_{n-1, k}^{i0})$, $F_{1}=F_{v}\cap V(Q_{n-1, k}^{i1})$, $f_{0}=|F_0|$ and $f_{1}=|F_1|$. Since $f_{v}=f_{0}+f_{1}$, consequently, $f_0\leq n-2$ and $f_1\leq n-2$.

Case 1 $x$ and $y$ are in the same subgraph. Without loss of generality, let $x, y\in Q_{n-1, k}^{i0}$. In $Q_{n-1, k}^{i0}$, $f_{0}\leq n-2$, by induction hypothesis, there exists a fault-free path $P_{0}(x, y)$ of length of at least $2^{n-1}-2f_{0}-1$ in $Q_{n-1, k}^{i0}-F_0$. We select an edge $(u, v)$ on path $P_{0}(x, y)$ such that $h(u, v)=1$, $\{u^{i}, v^{i}\}\in V(Q_{n, k}^{i1})$ and $\{u^{i}, v^{i}\}\cap f_{1}=\phi$. (If such an edge does not exit, then

$f_{1}\geq \lfloor \frac{2^{n-1}-2f_{0}-1}{2}\rfloor\geq\lfloor2^{n-2}-f_{0}-\frac{1}{2}\rfloor=2^{n-2}-f_{0}-1.$

Thus $f_{v}=f_{0}+f_{1}\geq2^{n-2}-1>n-2$, for $n\geq4$, which is a contradiction.) In $Q_{n-1, k}^{i1}$, it is to know $h(u^{i}, v^{i})=1$, and $f_{1}\leq n-2$, from induction hypothesis, there exists a fault-free path $P_{1}(u^{i}, v^{i})$ of length of at least $2^{n-1}-2f_{1}-1$ in $Q_{n-1, k}^{i1}-F_1$. Then a fault-free path connecting $x$ and $y$ of $Q_{n, k}$ can be constructed as $P(x, y)=P_{0}(x, u)\cup(u, u^{i})\cup P_{1}(u^{i}, v^{i})\cup(v^{i}, v)\cup P_{0}(v, y)$. The length of path $P(x, y)$ is at least

$(2^{n-1}-2f_{0}-1)-1+(2^{n-1}-2f_{1}-1)+2=2^{n}-2f_{v}-1$

(refer to Fig. 3 (a)).

Case 2  $x$ and $y$ are in the different subgraph. Without loss of generality, let $x\in Q_{n-1, k}^{i0}$, $y\in Q_{n-1, k}^{i1}$. In $Q_{n-1, k}^{i0}-F_{0}$, select $u$ be a neighbor of $x$ such that $u\neq \overline{x}$, $u$ be not adjacent to $y$, $u^{i}\in V(Q_{n-1, k}^{i1})$ and $u^{i}\cap f_{1}=\phi$ (if such an vertex does not exit, then

$f_{v}\geq\ \frac{2^{n-1}}{2} =2^{n-2}> n-2, $

for $n\geq 4$, which is a contradiction). In $Q_{n-1, k}^{i0}-F_{0}$, since $f_{0}\leq n-2$ and $h(x, u)=1$, by induction hypothesis, there exists a fault-free path $P_{0}(x, u)$ whose length is at least $2^{n-1}-2f_{0}-1$. Since $h(x, u)=1$, $h(u, u^{i})=1$ and $h(x, y)$ is odd, it is easy to know that $h(u^{i}, y)$ is odd. In $Q_{n-1, k}^{i1}-F_{1}$, since $f_{0}\leq n-2$ and $h(u^{i}, y)$ is odd, by induction hypothesis, there exists a fault-free path $P_{1}(u^{i}, y)$ of length of at least $2^{n-1}-2f_{1}-1$. Then a fault-free path connecting $x$ and $y$ of $Q_{n, k}$ can be constructed as $P(x, y)=P_{0}(x, u)\cup(u, u^{i})\cup P_{1}(u^{i}, y)$. The length of path $P(x, y)$ is at least

$(2^{n-1}-2f_{0}-1)+1+(2^{n-1}-2f_{1}-1)=2^{n}-2f_{v}-1$

(refer to Fig. 3 (b)).

By analyzing the above cases, the proof of the theorem is completed.

Theorem 2  Let $F_{v}$ be a set of $\mid F_{v}\mid =f_{v}=n$ faulty vertices in $Q_{n, k}$$(n\geq 3, 1\leq k\leq n-1)$ such that every vertex of $Q_{n, k}$ has at least two fault-free neighbors. Suppose that $x$ and $y$ are two vertices of with $h(x, y)=1$. Then there exists a fault-free path $P(x, y)$ of length of at least $2^{n}-2n-1$ in $Q_{n, k}-F_v$.

Proof  When $n=3$, $\mid F_{v}\mid =f_{v}=3$, it is not difficult to check the result for $Q_{3, 1}$ and $Q_{3, 2}$ holds. We show the theorem by induction on $n\geq 3$. According to Lemma 1 and Lemma 3, we can execute an $i(i<k)$-partition on $Q_{n, k}$ to obtain two $n$-dimensional enhanced hypercubes $Q_{n-1, k}^{i0}$ and $Q_{n-1, k}^{i1}$ such that each contains at least one faulty vertex. Since $x$ and $y$ be two adjacent vertices, without loss of generality, let $x$ and $y$ are in the same subgraph $Q_{n-1, k}^{i0}$. We will consider the following cases:

Case 1  $\mid F_{0}\mid =f_{0}=n-1$, $\mid F_{1}\mid =f_{1}=1$.

In $Q_{n-1, k}^{i0}$, $f_{0}=n-1$, by induction hypothesis, there exists a fault-free path $P_{0}(x, y)$ of length of at least $2^{n-1}-2f_{0}-1$ in $Q_{n-1, k}^{i0}-F_{0}$. We select an edge $(u, v)$ on path $P_{0}(x, y)$ such that $\{u^{i}, v^{i}\}\in V(Q_{n, k}^{i1})$ and $\{u^{i}, v^{i}\}\cap F=\phi$. In $Q_{n-1, k}^{i1}$, since $h(u^{i}, v^{i})=1$ and $f_{1}=1$, by theorem 1, there exists a fault-free path $P_{1}(u^{i}, v^{i})$ of length of at least $2^{n-1}-2f_{1}-1$ in $Q_{n-1, k}^{i1}-F_{1}$. Then a fault-free path $P(x, y)$ of $Q_{n, k}$ can be constructed as

$P(x, y)=P_{0}(x, u)\cup(u, u^{i})\cup P_{1}(u^{i}, v^{i})\cup(v^{i}, v)\cup P_{0}(v, y).$

The length of path $P(x, y)$ is at least $(2^{n-1}-2f_{0}-1)-1+2+(2^{n-1}-2f_{1}-1)=2^{n}-2n-1$.

Case 2 $2\leq \mid F_{0}\mid =f_{0}\leq n-2$, then $2\leq \mid F_{1}\mid =f_{1}\leq n-2$

In $Q_{n-1, k}^{i0}$, $f_{0}\leq n-2$, by Theorem 1, then there exists a fault-free path $P_{0}(x, y)$ of length of at least $2^{n-1}-2f_{0}-1$ in $Q_{n-1, k}^{i0}-F_{0}$. We select an edge $(u, v)$ on path $P_{0}(x, y)$ such that $\{u^{i}, v^{i}\}\in V(Q_{n, k}^{i1})$ and $\{u^{i}, v^{i}\}\cap F=\phi$. In $Q_{n-1, k}^{i1}$, since $2\leq f_{1}\leq n-2$, by Theorem 1, there exists a fault-free path $P_{1}(u^{i}, v^{i})$ of length of at least $2^{n-1}-2f_{1}-1$ in $Q_{n-1, k}^{i1}-F_{1}$. Then a fault-free path $P(x, y)$ of $Q_{n, k}$ can be constructed as

$P(x, y)=P_{0}(x, u)\cup(u, u^{i})\cup P_{1}(u^{i}, v^{i})\cup(v^{i}, v)\cup P_{0}(v, y).$

The length of path $P(x, y)$ is at least $(2^{n-1}-2f_{0}-1)-1+2+(2^{n-1}-2f_{1}-1)=2^{n}-2n-1$.

Case 3$\mid F_{0}\mid =f_{0}=1$, $\mid F_{1}\mid =f_{1}=n-1$.

In $Q_{n-1, k}^{i1}-F_{1}$, we can select an edge $(u^{i}, v^{i})\in E(Q_{n, k}^{i1})$ such that $h(u^{i}, v^{i})=1$, both $u^{i}$ and $v^{i}$ have at least two non-fault neighbor, $\{u, v\}\in V(Q_{n, k}^{i0})$ and $\{u, v\}\cap f=\phi$. By induction hypothesis, there exists a fault-free path $P_{1}(u^{i}, v^{i})$ of length of at least $2^{n-1}-2f_{1}-1$ in $Q_{n-1, k}^{i1}-F_{1}$. Since $Q_{n, k}$ contains $Q_{n}$ as its subgraph, then $Q_{n, k}-E_c\cong Q_n$. In $Q_{n-1, k}^{i0}$, by Lemma 6, there exists a fault-free path $P_{0}(x, y)$ that contains edge $(u, v)$ in $Q_{n-1, k}^{i0}-E_{c}-F_{1}$ which is also in $Q_{n-1, k}^{i0}-F_{1}$. Then a fault-free path $P(x, y)$ of $Q_{n, k}$ can be constructed as

$P(x, y)=P_{0}(x, u)\cup(u, u^{i})\cup P_{1}(u^{i}, v^{i})\cup(v^{i}, v)\cup P_{0}(v, y).$

The length of path $P(x, y)$ is at least $(2^{n-1}-2f_{0}-1)-1+2+(2^{n-1}-2f_{1}-1)=2^{n}-2n-1$.

In this subsection, we demonstrate there exist the vertex-fault-tolerant cycles embedding on enhanced hypercube when $1 \leq |F_v|=f_v\leq 2n-3$.

Theorem 3  Let $F_v$ be the faulty vertex set of $Q_{n, k}$ such that every vertex of $Q_{n, k}$ has at least two fault-free neighbors, where $n\geq 4$ and $1 \leq |F_v|=f_v\leq 2n-3$, then there exists a fault-free cycle, which is of even length of at least $2^n-2f_v$ in $Q_{n, k}-F_v$, if $n$ and $k$ have same parity.

Proof  When $n=4$, $1\leq |F_v|\leq 2n-3=5$, we consider $Q_{4, k}$. By Lemma 4, it is obviously hold for $Q_{4, k}$ when $1\leq |F_v|\leq 2n-4=4$. Consequently, we only need to consider $|F_v|=5$ in $Q_{4, k}$. Applying lemma 1, $Q_{n, k}$ can be partitioned into two $(n-1)$-dimensional hypercube $Q_{n-1}^{i0}$ and $ Q_{n-1}^{i1}$ along some component $i( i \geq k)$ such that one contains a fault vertex. In the following, For a faulty vertex set $F_{v}$, let $f_{v}=|F_v|$, where $F_{v}\subset V(Q_{n})$. Let $F_{0}=F_{v}\cap V(Q_{n-1}^{i0})$ and $F_{1}=F_{v}\cap V(Q_{n-1}^{i1})$. Let $f_{0}=|F_0|$ and $f_{1}=|F_1|$.

Case 1 $|F_0|=f_0=4$, $|F_1|=f_1=1$.

Select a vertex $x\in V(Q_{3}^{i0})$ such that $x\cap \{F_{0}\}=\emptyset$, $\bar{x}\in V(Q_{3}^{i1})$, $x^i\in V(Q_{3}^{i1})$ and $\{\bar{x}, x^i\}\cap F_1=\emptyset$. Since $h(x, \bar{x})=n-k+1$ and $h(x, x^i)=1$, we have $h(\bar{x}, x^i)=n-k$. Since $n$ and $k$ have same parity, then $h(\bar{x}, x^i)$ is even. In $Q_{3}^{i1}$, by Lemma 7, there exists a fault-free path $P_1(\bar{x}, x^i)$ of even length $2^{3}-2\times1-2=4$ connecting $\bar{x}$ and $x^i$ in $Q_{3}^{i1}-F_1$. The desired even cycles can be constructed as $(x, \bar{x})\cup P_1(\bar{x}, x^i)\cup (x^i, x)$, whose length is $6$ (refer to Fig. 4 (a)).

Case 2 $|F_0|=f_0=3$, $|F_1|=f_1=2$.

In $Q_{3}^{i0}$, select an edge $(x, y)\in E(Q_{3}^{i0})$ such that $h(x, y)=1$ and $\{x^i, y^{i}\}\cap F_1=\emptyset$. In $Q_{3}^{i1}$, by Lemma 9, there exists a fault-free path $P_{1}(x^{i}, y^{i})$ of length of at least $2^{3}-5=3$ in $Q_{3}^{i1}-F_1$. Then the desired even cycles can be constructed as $(x, y)\cup(y, y^{i})\cup P_1(y^{i}, x^i)\cup (x^i, x)$, whose length is $6$ (refer to Fig. 4 (b)).

When $n\geq 5$, $1\leq |F_v|=f_v\leq 2n-3$. In $Q_{n, k}-E_c$, since $Q_{n, k}-E_c\cong Q_n$, by Lemma 4 and Lemma 5, there exist fault-free cycles of even length at least $2^n-2f$ in $Q_{n, k}-E_c-F_v$ which is also in $Q_{n-1, k}^{i0}-F_{1}$.

The proof of the theorem is completed.

Theorem 4   Let $F_v$ be the faulty vertex set of $1\leq |F_v|=f_v\leq 2n-3$ in $Q_{n, k}$ such that every vertex of $Q_{n, k}$ has at least two fault-free neighbors, $n$ and $k$ have different parity. Then there exists a fault-free cycle, which is of even length of at least $2^n-2f_v$ in $Q_{n, k}-F_v$, if $n\geq 4$; and simultaneously, there exists a fault-free cycle, which is of odd length of at least $2^n-2f_v+1$ in $Q_{n, k}-F_v$, if $n\geq 3$.

Proof  We proceed by induction on $n$. Let $w$ and $z$ are two distinct faulty vertices. Applying Lemma 1 and Lemma 3, $Q_{n, k}$ can be partitioned into two $(n-1)$-dimensional enhanced hypercube $Q_{n-1, k}^{i0}$ and $ Q_{n-1, k}^{i1}$ along some component $i( i < k)$ such that one contains the vertex $w$ and the other contains the vertex $z$. In the following, For a faulty set $F=F_{v}\cup F_{e}$, let $f_{v}=|F_v|$ and $f_{e}=|F_e|$, where $F_{v}\subset V(Q_{n, k})$ and $F_{e}\subset E(Q_{n, k})$. Let $F_{0}=F_{v}\cap V(Q_{n-1, k}^{i0})$ and $F_{1}=F_{v}\cap V(Q_{n-1, k}^{i1})$. Let $f_{0}=|F_0|$ and $f_{1}=|F_1|$.

Case 1 We first proof $Q_{n, k}-F_{v}$ contains a fault-free cycle of even length of at least $2^n-2f_v$ if $n\geq 4$.

When $n=4$, $1\leq |F_v|\leq 2n-3=5$, we consider $Q_{4, k}$. By Lemma 4, it is obviously hold for $Q_{4, k}$ when $1\leq |F_v|\leq 2n-4=4$, consequently, in the following, we only need to consider $|F_v|=5$ in $Q_{4, k}$.

Case 1.1 $|F_0|=f_0=4$, $|F_1|=f_1=1$.

Select an edge $(x, y)\in E(Q_{3, k}^{i0})$ such that $h(x, y)=1$ and $\{x^i, y^{i}\}\cap F_1=\emptyset$. In $Q_{3, k}^{i1}$, since $f_1=1$, by theorem 1, there exists a fault-free path $P_{1}(x^{i}, y^{i})$ of length of at least $2^{3}-2\times2-1=3$ in $Q_{3, k}^{i1}-F_1$. Then the desired even cycles can be constructed as $(x, y)\cup(y, y^{i})\cup P_1(y^{i}, x^i)\cup (x^i, x)$, whose length is $6$.

Case 1.2 $|F_0|=f_0=3$, $|F_1|=f_1=2$.

In $Q_{3, k}^{i0}$, select an edge $(x, y)\in E(Q_{3, k}^{i0})$ such that $h(x, y)=1$ and $\{x^i, y^{i}\}\cap F_1=\emptyset$. In $Q_{3, k}^{i1}$, since $f_1=2$, by Theorem 1, there exists a fault-free path $P_{1}(x^{i}, y^{i})$ of length of at least $2^{3}-2\times2-1=3$ in $Q_{3, k}^{i1}-F_1$. Then the desired even cycles can be constructed as $(x, y)\cup(y, y^{i})\cup P_1(y^{i}, x^i)\cup (x^i, x)$, whose length is $6$.

When $n\geq 5$, $1\leq |F_v|=f_v\leq 2n-3$. In $Q_{n, k}-E_c$, since $Q_{n, k}-E_c\cong Q_n$, by Lemma 4 and Lemma 5, there exist fault-free cycles of even length at least $2^n-2f$ in $Q_{n, k}-E_c-F_v$ which is also in $Q_{n-1, k}^{i0}-F_{1}$.

Case 2  In the following, we proof $Q_{n, k}-F_{v}$ contains a fault-free cycle of odd length of at least $2^n-2f_v+1$ if $n\geq 3$.

For $n=3$, $1\leq|F_v|\leq 2n-4=3$, since $n$ and $k$ have different parity, we only need to consider $Q_{3, 2}$. When $f_{v}=1$, without loss of generality, we can select an arbitrary vertex $u=000$ as a faulty vertex, then we can easily construct a odd length fault-free cycle as $C=(100, 111, 101, 001, 011, 010, 110, 110)$ in $Q_{3, 2}-u$, whose length is $7$. When $f_{v}=2$, if the two faulty vertex are adjacent, since $Q_{3, 2}$ is vertex-symmetric, we may assume that $x=000$ and $y=001$. then a fault-free path of odd length 5 is constructed as follows: (100, 110, 010, 011, 111, 100). If the two faulty vertex are not adjacent, because of the symmetric of $Q_{3, 2}$, let $f_{1}=000$ and $f_{2}=111$, then a fault-free path of odd length 5 is constructed as follows: (010, 001, 101, 100, 110, 010). When $f_{v}=3$, by the structure of $Q_{3, 2}$, we can easily construct a fault-free cycle of odd length 3. In the following, we want to construct a fault-free cycle, which is of odd length of at least $2^n-2f_v+1$ in $Q_{n, k}-F_v$.

Case 2.1  $1\leq |F_v|=f_v\leq n-1$. Since $f_{v}=f_{0}+f_{1}$, consequently, $1\leq f_0\leq n-2$ and $1\leq f_1\leq n-2$.

Select an edge $(x, y)$ in $E(Q_{n-1, k}^{i0})$ such that $\{x, y\}\cap F_{0}=\emptyset$, $\{\bar{x}, y^{i}\}\in V(Q_{n-1}^{i1})$ and $\{\bar{x}, y^{i}\}\cap F_{1}=\emptyset$. In $Q_{n-1, k}^{i0}-F_{0}$, since $h(x, y)=1$ and $f_0\leq n-2$, by Theorem 1, there exists a fault-free path $P_{0}(x, y)$ of length of at least $2^{n-1}-2f_{0}-1$ in $Q_{n-1, k}^{i0}-F_0$. In $Q_{n-1, k}^{i1}-F_{1}$, Select $u$ be a neighbor of $\bar{x}$ such that $u\neq y^{i}$. (If such an vertex does not exit, then $f_{1}\geq\ \frac{2^{n-1}}{2} =2^{n-2}> n-2$, for $n\geq 3$, which is a contradiction.) Since $h(x, \bar{x})=n$ and $n$ is even, then $h(x, \bar{x})$ is even. And $h(y, y^{i})=1$<, <$h(\bar{x}, u)=1$, consequently, $h(u, y^{i})$ is odd, and $f_1\leq n-2$, by Theorem 1, there exists a fault-free path $P_{1}(u, y^{i})$ of length of at least $2^{n-1}-2f_{1}-1$ in $Q_{n-1, k}^{i1}-F_1$. Then the desired odd cycles can be constructed as

$(x, \bar{x})\cup (\bar{x}, u)\cup P_{1}(u, y^{i})\cup(y^{i}, y)\cup P_{0}(y, x)$

of length of at least

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

(refer to Fig. 5).

Case 2.2  $n\leq |F_v|=f_v\leq 2n-3$.

Case 2.2.1  $|F_0|=f_0=2n-4$, $|F_1|=f_1=1$.

Let $w$ be a fault vertex in $Q_{n-1, k}^{i0}$. Imagining $w$ not faulty, consequently, $|F_0|=f_0\leq 2n-5$, by induction hypothesis, there exists a fault-free cycle $C_{0}$ of length of at least $2^{n-1}-2(f_{0}-1)+1$ in $Q_{n-1, k}^{i0}-F_0$.

Case 2.2.1.1  $w\in C_{0}$, select $x, y\in C$ be adjacent to $w$ such that $h(x, y)=2$ and $\{x^{i}, y^{i}\}\in V(Q_{n-1, k}^{i0})$.

When $\{x^{i}, y^{i}\}\cap F=\phi$. In $Q_{n-1, k}^{i1}$, $h(x^{i}, y^{i})$ is even, by Lemma 7, there exists a fault-free path $P_{1}(x^{i}, y^{i})$ of length of at least $2^{n-1}-2f_{1}-2$ in $Q_{n, k}^{i1}-F_1-E_{c}$ which is also in in $Q_{n, k}^{i1}-F_1$. Then a fault-free cycle $C$ of $Q_{n, k}$ can be constructed as $C=(C_{0}-xy)\cup(y, y^{i})\cup P_{1}(y^{i}, x^{i})\cup(x^{i}, x)$. The length of cycle $C$ is at least

$(2^{n-1}-2(f_{0}-1)+1)-2+2+(2^{n-1}-2f_{1}-2)=2^{n}-2f_{v}+1$

(refer to Fig. 6 (a)).

When $\{x^{i}, y^{i}\}\cap F\neq \phi$. Without loss of generality, let $x^{i}$ is faulty. Select $u\in C$ be adjacent to $x$ such that $h(u, y)=3$, then $u^{i}$ is not fault. In $Q_{n, k}^{i1}$, by Theorem 1, there exists a fault-free path $P(u^{i}, y^{i})$ of length of at least $2^{n-1}-2f_{1}-1$ in $Q_{n-1, k}^{i1}-F_1$. Then a fault-free cycle of $Q_{n, k}$ can be constructed as $C=C_{0}-uy\cup(u, u^{i})\cup P_{1}(u^{i}, y^{i})\cup(y^{i}, y)$. The length of cycle is at least $(2^{n-1}-2(f_{0}-1)+1)-3+2+(2^{n}-2f_{1}-1)=2^{n}-2f_{v}+1$ (refer to Fig. 6 (b)).

Case 2.2.1.2 $w\notin C_{0}$, We select an edge $(x, y)$ in $C_{0}$ $Q_{n-1, k}^{i0}$ such that $h(x, y)=2$ and $\{x^{i}, y^{i}\}\cap F=\phi$. In $Q_{n-1, k}^{i1}$, $h(x^{i}, y^{i})$ is even, by Lemma 7, there exists a fault-free path $P_{1}(x^{i}, y^{i})$ of length of at least $2^{n-1}-2f_{1}-2$ in $Q_{n-1, k}^{i1}-F_1-E_{c}$ which is also in in $Q_{n, k}^{i1}-F_1$. Then a fault-free cycle of $Q_{n, k}$ can be constructed as $C=(C_{0}-xy)\cup(y, y^{i})\cup P_{1}(y^{i}, x^{i})\cup(x^{i}, x)$. The length of cycle is at least $(2^{n-1}-2(f_{0}-1)+1)-2+2+(2^{n-1}-2f_{1}-2)=2^{n}-2f_{v}+1$.

Case 2.2.2  $n-1\leq |F_0|=f_0\leq 2n-5$, $1\leq |F_1|=f_1=n-2$.

In $Q_{n-1, k}^{i0}$, by induction hypothesis, there exists a fault-free cycle $C_{0}$ of length of at least $2^{n-1}-2f_{0}+1$ in $Q_{n-1, k}^{i0}-F_{0}$. We select an edge $(x, y)$ in cycle $C_{0}$ of $Q_{n, k}^{i0}$ such that $h(x, y)=1$ and $\{x^{i}, y^{i}\}\cap F=\phi$. (If such an edge does not exit, then $f_{1}\geq \lfloor \frac{2^{n}-2f_{0}-1}{2}\rfloor\geq\lfloor2^{n-1}-f_{0}-\frac{1}{2}\rfloor=2^{n-1}-f_{0}-1$. Thus $f_{1}\geq 2^{n-1}-(2n-5)-1>n-2$, for $n\geq3$, which is a contradiction.) In $Q_{n-1, k}^{i1}$, $h(x^{i}, y^{i})=1$, by theorem 1, there exists a fault-free path $P_{1}(x^{i}, y^{i})$ of length of at least $2^{n-1}-2f_{1}-1$ in $Q_{n-1, k}^{i1}-F_{1}$. Then a fault-free cycle of $Q_{n, k}$ can be constructed as $C=(C_{0}-xy)\cup(y, y^{i})\cup P_{1}(y^{i}, x^{i})\cup(x^{i}, x)$. The length of cycle is at least $(2^{n}-2f_{0}+1)-1+2+(2^{n-1}-2f_{1}-1)=2^{n}-2f_{v}+1$.

Case 2.2.3  $|F_0|=f_{0}= n-2, 1\leq |F_1|=f_{1}\leq n-1$.

When $f_{1}\leq n-2$. The discussion is similar to case 2.2.2. So we next only need to discuss the case of $|F_1|=f_{1}=n-1$. In $Q_{n-1, k}^{i0}$, by induction hypothesis, there exists a fault-free cycle $C_{0}$ of length of at least $2^{n-1}-2f_{0}+1$ in $Q_{n-1, k}^{i0}$. We select an edge $(x, y)$ in cycle $C_{0}$ such that $h(x, y)=1$ and $\{x^{i}, y^{i}\}\cap F=\phi$ (if such an edge does not exit, then $f_{1}\geq \lfloor \frac{2^{n}-2f_{0}-1}{2}\rfloor\geq\lfloor2^{n-1}-f_{0}-\frac{1}{2}\rfloor=2^{n-1}-f_{0}-1$. Thus $f_{1}\geq 2^{n-1}-(n-2)-1>n-1$, for $n\geq3$, which is a contradiction). In $Q_{n-1, k}^{i1}$, by Theorem 2, there exists a path $P_{1}$ of length at least $2^{n-1}-2f_{1}-1$ in $Q_{n-1, k}^{i1}-F_{1}$. Then a fault-free cycle of $Q_{n, k}$ can be constructed as $C=(C_{0}-xy)\cup(y, y^{i})\cup P_{1}(y^{i}, x^{i})\cup(x^{i}, x)$. The length of cycle is at least $(2^{n-1}-2f_{0}+1)-1+2+(2^{n-1}-2f_{1}-1)=2^{n}-2f_{v}+1$.

Therefore the proof is completed.

Since every component in the muti-process computer systems may have different reliability, it is important to consider properties of a network with some conditional faults. Consequently, choosing network topology is an important issue in the design of computer networks. Among many different choices, the enhanced hypercube is an important network topology for parallel processing computer systems. In this paper, we consider fault-tolerant path and cycle embedding in $Q_{n, k}$. First, for $Q_{n, k}$ with $|F_v|=f_{v}\leq n-1$ faulty vertices, there exists a fault-free path with length $2^n-2f_{v}-1$ between two arbitrary vertices of odd distance, where $n\geq 3$. Furthermore, for $Q_{n, k}$ with $1\leq|F_v|=f_v\leq2n-3$ and every vertex of $Q_{n, k}$ has at least two fault-free neighbors, there exists a fault-free cycle of even length of at least $2^n-2f_v$, if $n\geq 4$; and simultaneously, when $n$ and $k$ have different parity, there exists a fault-free cycle of odd length of at least $2^n-2f_v+1$ in $Q_{n, k}-F_v$, if $n\geq 3$. The result that an odd cycle can be embedded into $Q_{n, k}$ when $n$ and $k$ have different parity shows that is superior to $Q_{n}$ in view of the cycle embedding capability. These good properties imply that the reliability and fault tolerance of $Q_{n, k}$ are better than the hypercube, which shows that the $Q_{n, k}$ is an excellent choice of network topology for parallel processing computer systems. It is then concluded that interconnection networks modeled by enhanced hypercube are extremely efficient and robust.

As compared to [14], this paper significantly improves the number of faulty nodes tolerable. Since the enhanced hypercube is bipartite when $n$ and $k$ have same parity (see [28]) and the connectivity of an enhanced hypercube is $n+1$, whereas the connectivity of hypercube is $n$. Hence, our result is optimal. This paper reveals that a enhanced hypercube may tolerate faulty vertices more than its connectivity. To embed fault-free cycles in the enhanced hypercube with more faulty vertices or edges is one of our further projects.