0 Introduction

Network topology is usually represented by a graph where vertices represent processor and edges represent links between processors^[1].The hypercube has been widely used as the interconnection network in parallel computers^{[2, 3]}.The n-dimensional generalized hypercube, denoted by Q(d₁, d₂, …, d_n), where d_i(≥2) is an integer for each i=1, 2, …, n.The vertex-set of Q(d₁, d₂, …, d_n) is the set V={x₁x₂…x_n: x_i∈{0, 1, …, d_i-1}, i=1, 2, …, n} and two vertices x=x₁x₂…x_n and y=y₁y₂…y_n are linked by an edge if and only if they differ exactly in one coordinate.If d₁=d₂=…=d_n=d≥2, then Q (d, d, …, d) is called the d-ary n-dimensional cube, denoted by Q_n(d).It is clear that Q_n(2) is hypercube Q_n.For two vertices u and v in Q_n(d), the Hamming distance h(u, v) between two vertices u and v is the number of different bits in the corresponding strings of both vertices; and the distance between u and v, denoted by D(Q_n(d); u, v), is the length of the shortest path between u and v.Obviously, h(u, v)=D(Q_n(d); u, v).Let u=u₁u₂…u_n be a vertex of Q_n(d), u^j(a)=v=v₁v₂…v_n is also a vertex of Q_n(d), v_i=u_i (1≤i≤n, i≠j, j∈{1, 2, …, n}), v_j≠u_j, v_j=a∈{0, 1, 2, …, d-1}.A vertex is fault-free if it is not faulty.An edge is fault-free if the two end-vertices and the link between them are not faulty.A cycle of length k is called k-cycle.A graph G is vertex-transitive if for any given pair (x, y) of vertices in G there is some θ∈Aut(G)(Aut(G) is an automorphism group of G) such that y=θ(x).

The cycle embedding problem deals with all possible lengths of the cycles in a given graph, it is investigated in a lot of interconnection networks^[4].The fault-tolerant capacity of an interconnection network is a critical issue in parallel computing^[2].For hypercube Q_n, Saad and Schultz^[5] proved that an even cycle of length k exists for each even integer between 4 and 2ⁿ.Let f_e (respectively, f_v) be the number of faulty edges (respectively, vertices) in Q_n.If f_e≤n-2, Li et al.^[1] proved that every fault-free edge of Q_n(n≥3) lies on a fault-free cycle of every even length from 4 to 2ⁿ.If f_e≤n-1 and all faulty edges are not incident with the same vertex, Xu et al.^[6]showed that every fault-free edge of Q_n (n≥4) lies on a fault-free cycle of every even length from 6 to 2ⁿ.Fu^[7] proved that a fault-free cycle of length with at least 2ⁿ-2f_v can be embedded in Q_n with f_v≤2n-4.If f_v≤2n-2, Tsai^[2] proved that every fault-free edge and fault-free vertex of Q_n lies on a fault-free cycle of every even length from 4 to 2ⁿ-2f_v.Stewart and Xiang^[8] studied the bipanconnectivity and bipancyclicity in k-ary n-cubes.Cheng et al.^[9] studied the vertex-fault-tolerant cycles embedding in balanced hypercubes with faulty edges; Hao et al.^[10] studied the hamiltonian cycle embedding for fault tolerance in balanced hypercubes.

In this article, we study the cycle embedding in Q_n(d).For any subset F of V(Q_n(d))(n≥3) with |F|≤n-2, we prove that every fault-free edge and fault-free vertex (node) of Q_n(d) lies on a fault-free cycle of every even length from 4 to dⁿ-2|F|.If d=2, these results are the results of Tsai^[2].

1 Preliminaries

The n-bit Gray code is a ring sequence of n-bit numbers (the number of each coordinate is selected from {0, 1, 2, …, d-1}) such that any two successive numbers have one and only one different bit and so that all numbers having n bits are represented.The n-bit Gray code is denoted by G_n.If d is an even number.One starts with the sequence of the d 1-bit numbers 0, 1, 2, …, d-1.This is a 1-bit Gray code, i.e., G₁={0, 1, 2, …, d-1}.To obtain a 2-bit Gray code G₂, take the same sequence and insert a zero in front of each number, then take the sequence in reverse order and insert a one in front of each number, take the same sequence and insert a 2 in front of each number, then take the sequence in reverse order and insert a 3 in front of each number, take the same sequence and insert a d-2 in front of each number, then take the sequence in reverse order and insert a d-1 in front of each number.In other words, from G₁={0, 1, 2, …, d-1}, we get a 2-bit Gray code G₂={00, 01, …, 0(d-2), 0(d-1), 1(d-1), 1(d-2), …, 11, 10, …, (d-2)0, (d-2)1, …, (d-2)(d-2), (d-2)(d-1), (d-1)(d-1), (d-1)(d-2), …, (d-1)1, (d-1)0}.More generally, denoted by G_n^R the sequence obtained from G_n by reversing its order, and by mG_n, m=0, 1, 2, …, d-1 (respectively, mG_n^R) the sequence obtained from G_n by inserting a m in front of each element of the sequence, then an (n+1)-bit Gray code can be generated by the recursion G_n+1={0G_n, 1G_n^R, 2G_n, 3G_n^R, …, (d-2)G_n, (d-1)G_n^R}.If d is an odd number, Gray codes can be similar to generate.

Let V_n be the set of vertices of Q_n(d).For a given i(0≤i≤d-1), let iV_n-1 be the subset of vertices of Q_n(d) whose fist coordinate is i.Thus the set of vertices of Q_n(d) can be decomposed into d disjoint subsets 0V_n-1, 1V_n-1, …, (d-1)V_n-1.We use iQ_n-1(d) to denote the subgraph of Q_n(d) induced by iV_n-1.Then iQ_n-1(d) is isomorphic to Q_n-1(d).It is often convenient to write Q_n(d)=0Q_n-1(d)Θ1Q_n-1(d)Θ…Θ(d-1)Q_n-1(d).

Lemma   1      Let u and v be two distinct vertices of Q_n(d).Then, there is a partition which can partition Q_n(d) into d copies Q_n-1(d), denoted by Q_n-1ⁱ(d) i 0, 1, …, d-1) such that u∈V(Q_n-1^m(d)) and v∈V(Q_n-1^k(d))(m, k∈{0, 1, 2, …, d-1}, m≠k}.

Proof      Let u=u₁u₂…u_n and v=v₁v₂…v_n.Since u and v are distinct vertices, there is an index j(j∈{1, 2, …, n} such that u_j≠v_j, u_j∈{0, 1, …, d-1}, v_j∈{0, 1, …, d-1}.Therefore, Q_n(d) can be partitioned along dimension j into d copies Q_n-1(d) such that one contains u and the other contains v.

Lemma   2      Let e=(u, v) be an edge of Q_n(d).Then, there is a partition which can partition Q_n(d) into d copies Q_n-1(d), denoted by Q_n-1ⁱ(d)(i=0, 1, …, d-1) such that u∈V(Q_n-1^m(d)) and v∈V(Q_n-1^m(d))(m∈{0, 1, 2, …d-1}), i.e., e is an edge of Q_n-1^m(d).

Proof      Let e=(u, v) be an edge of Q_n(d), u=u₁u₂…u_n, v=v₁v₂…v_n, then, there is an index i(i∈{1, 2, …, n}) such that u_i≠v_i, u_j=v_j(1≤j≤n, j≠i).Therefore, Q_n(d) can be partitioned along dimension j into d copies Q_n-1(d) such that e∈E(Q_n-1^m(d))(m∈{0, 1, 2, …, d-1}).

2 d is an even number

Theorem   1     Let x and y be any two vertices in Q_n(d)(n≥2) and l be any integer with D(Q_n(d); x, y)≤l≤dⁿ-1.If d is an even number and l-D(Q_n(d); x, y) is also an even number, then there is an xy-path of length l in Q_n(d).

Proof     Let D(Q_n(d); x, y)=m.The proof is based on the recursive structure of Q_n(d) by induction on n≥2.When n=2, if D(Q₂(d); x, y)=1.By the vertex-transitivity of Q₂(d)^[3], without loss of generality, we can assume x=00, y=01.

x=00→01=y, x=00→02→03→01=y, x=00→02→03→04→05→01=y, …, x=00→02→03→04→05→…→0(d-2)→0(d-1)→01=y are the xy-path of length l=1, 3, 5, …, d-1 in Q₂(d).

x=00→10→12→02→03→04→05→…→0(d-2)→0(d-1)→01=y.x=00→10→20→22→12→02→03→04→05→…→0(d-2)→0(d-1)→01=y.….x=00→10→20→30→40→…→(d-2)0→(d-1)0→(d-1)2→(d-2)2→…→22→12→02→03→04→05→…→0(d-2)→0(d-1)→01=y.….x=00→10→20→30→40→…→(d-2)0→(d-1)0→(d-1)2→(d-2)2→…→22→12→02→03→13→23→…→(d-2)3→(d-1)3→(d-1)4→(d-2)4→…→24→14→04→05→…→0(d-1)→1(d-1)→2(d-1)→…→(d-2)(d-1)→(d-1)(d-1)→(d-1)1→(d-2)1→…→21→11→01=y are the xy-path of length l=d+1, d+3, …, 3(d-1), …, d²-1 in Q₂(d).

When n=2, if D(Q₂(d); x, y)=2.By the vertex-transitivity of Q₂(d)^[3], without loss of generality, we can assume x=00, y=11.

x=00→10→11=y, x=00→20→30→10→11=y.x=00→20→30→40→50→10→11=y.….x=00→20→30→40→50→…→(d-2)0→(d-1)0→10→11=y are the xy-path of length l=2, 4, 6, …, d in Q₂(d).

x=00→01→21→20→30→40→50→…→(d-2)0→(d-1)0→10→11=y.x=00→01→02→22→21→20→30→40→50→…→(d-2)0→(d-1)0→10→11=y.….x=00→01→02→…→0(d-2)→0(d-1)→2(d-1)→2(d-2)→…→22→21→20→30→40→…(d-3)0→(d-2)0→(d-1)0→10→11=y.….x=00→01→02→…→0(d-2)→0(d-1)→2(d-1)→2(d-2)→…→22→21→20→30→31→32→…→3(d-2)→3(d-1)→4(d-1)→4(d-2)→…→42→41→40→…→(d-3)0→(d-3)1→(d-3)2→…→(d-3)(d-2)→(d-3)(d-1)→(d-2)(d-1)→(d-2)(d-2)→…→(d-2)2→(d-2)1→(d-2)0→(d-1)0→(d-1)2→(d-1)3→…→(d-1)(d-2)→(d-1)(d-1)→1(d-1)→1(d-2)→…→13→12→10→11=y are the xy-path of length l=d+2, d+4, …, 3d-2, …, d²-2 in Q₂(d).

Assuming the theorem holds for any k with 2≤k < n.Let x=x₁x₂…x_n and y=y₁y₂…y_n be any two vertices with distance m in Q_n(d) and let l be an integer with m≤l≤dⁿ-1 and l-m is an even number.Let Q_n(d)=0Q_n-1(d)Θ1Q_n-1(d)Θ…Θ(d-1)Q_n-1(d).

Case   1      m < n

By the vertex-transitivity of Q_n(d)^[3], without loss of generality, we can assume x, y∈V(0Q_n-1(d)).By the induction hypothesis, there is an xy-path of length l in Q_n(d), where m≤l≤d^n-1-1.

Assuming d^n-1≤l≤2×d^n-1-1.Let P₀ be the longest xy-path in 0Q_n-1(d), the length of P₀ is l_P0 and l_P0-m is an even number.We have l_P0=d^n-1-1 if m is odd and l_P0=d^n-1-2 if m is even.Let l₁=l-l_P0-1.Then l₁ is odd and less than d^n-1.Let uv be any edge in P₀, and u, v∈0Q_n-1(d), u≠x, u≠y, v≠x, v≠y.Then P₀=P_0xu+uv+P_0vy.Let u′ and v′ be neighbors of u and v in 1Q_n-1(d).By the induction hypothesis, there is a u′v′-path P₁ of length l₁ in 1Q_n-1(d).Then P_0xu+uu′+P₁+v′v+P_0vy is an xy-path of length l in 0Q_n-1(d)Θ1Q_n-1(d), this is also an xy-path of length l in Q_n(d).

Assuming 2×d^n-1≤l≤3×d^n-1-1.Let P₀₁ be the longest xy-path in 0Q_n-1(d)Θ1Q_n-1(d), the length of P₀₁ is l_P01 and l_P01-m is an even number.We have l_P01=2×d^n-1-1 if m is odd and l_P01=2×d^n-1-2 if m is even.Let l₂=l-l_P01-1.Then l₂ is odd and less than d^n-1.Let u₁v₁ be any edge in P₀₁, and u₁, v₁∈1Q_n-1(d), u₁≠u′, u₁≠v′, v₁≠u′, v₁≠v′.Then P₀₁=P_01xu1+u₁v₁+P_01v1y.Let u′₁ and v₁′ be neighbors of u₁ and v₁ in 2Q_n-1(d).By the induction hypothesis, there is an u′₁v₁′-path P₂ of length l₂ in 2Q_n-1(d).Then P_01xu1+u₁u₁′+P₂+v₁′v₁+P_01v1y is an xy-path of length l in 0Q_n-1(d)Θ1Q_n-1(d)Θ2Q_n-1(d), this is also an xy-path of length l in Q_n(d).

…, …, …

Assuming (d-1)×d^n-1≤l≤dⁿ-1.Let P_01…(d-2) be the longest xy-path in 0Q_n-1(d)Θ1Q_n-1(d)Θ…Θ(d-2)Q_n-1(d), the length of P_01…(d-2) is l_P01…(d-2) and l_P01…(d-2)-m is an even number.We have P_01…(d-2)=(d-1)×d^n-1-1 if m is odd and P_01…(d-2)=(d-1)×d^n-1-2 if m is even.Let l_d-1=l-l_P01…(d-2)-1.Then l_d-1 is odd and less than d^n-1.Let u_d-2v_d-2 be any edge in P_01…(d-2), and u_d-2, v_d-2∈(d-2)Q_n-1(d), u_d-2≠u′_d-3, u_d-2≠v′_d-3, v_d-2≠u′_d-3, v_d-2≠v′_d-3.Then P_01…(d-2)=P_{01…(d-2)xu→d-2}+u_d-2v_d-2+P_{01…(d-2)v→d-2}y.Let u′_d-2 and v′_d-2 be neighbors of u_d-2 and v_d-2 in (d-1)Q_n-1(d).By the induction hypothesis, there is an u′_d-2v′_d-2-path P_d-1 of length l_d-1 in (d-1)Q_n-1(d).Then P_{01…→(d-2)xu→d-2}+u_d-2u′_d-2+P_d-1+v′_d-2v_d-2+P_{01…(d-2)v→d-2}yis an xy-path of length l in Q_n(d).

Case   2      m=n

By the vertex-transitivity of Q_n(d)^[3], without loss of generality, we can assume x∈V(0Q_n-1(d)), y∈V(1Q_n-1(d)).Let v be a neighbor of y in 1Q_n-1(d), u be the neighbor of v in 0Q_n-1(d).Then D(Q_n-1(d); x, u)=n-2.

If n≤l≤d^n-1+1.By the induction hypothesis, there is an xu-path P of length l-2 in 0Q_n-1(d), Then P+uv+vy is an xy-path of length l in Q_n(d).

If d^n-1+2≤l≤2×d^n-1-1.Let P₀ be the longest xu-path in 0Q_n-1(d), the length of P₀ is l_P0 and l_P0-m is an even number.We have l_P0=d^n-1-1 if m is odd and l_P0=d^n-1-2 if m is even.Let l₁=l-l_P0-1.Then l₁ is odd and less than d^n-1.By the induction hypothesis, there is a vy-path P₁ of length l₁ in 1Q_n-1(d).Then P₀+uv+P₁ is an xy-path of length l in 0Q_n-1(d)Θ1Q_n-1(d), this is also an xy-path of length l in Q_n(d).

If 2×d^n-1≤l≤3×d^n-1-1.Let P₀₁ be the longest xy-path in 0Q_n-1(d)Θ1Q_n-1(d), the length of P₀₁ is l_P01 and l_P01-m is an even number.We have l_P01=2×d^n-1-1 if m is odd and l_P01=2×d^n-1-2 if m is even.Let l₂=l-l_P01-1.Then l₂ is odd and less than d^n-1.Let u₁v₁ be any edge in P₀₁, and u₁, v₁∈1Q_n-1(d), u₁≠v, u₁≠y, v₁≠v, v₁≠y.Then P₀₁=P_01xu1+u₁v₁+P_01v1y.Let u′₁ and v′₁ be neighbors of u₁ and v₁ in 2Q_n-1(d).By the induction hypothesis, there is an u′₁v′₁-path P₂ of length l₂ in 2Q_n-1(d).Then P_01xu1+u₁u′₁+P₂+v′₁v₁+P_01v1y is an xy-path of length l in 0Q_n-1(d)Θ1Q_n-1(d)Θ2Q_n-1(d), this is also an xy-path of length l in Q_n(d).

The rest of the proof is similar to Case 1.

By the induction principle, the theorem follows.

Applying Theorem 1, we have

Corollary   1      For any n≥2, every edge of Q_n(d)(d≥2, d is an even number) lies on a cycle of every even length from 4 to dⁿ.

Applying Theorem 1.If d=2, we have

Corollary   2 ^{[1, 3]}     Let x and y be any two vertices in Q_n(n≥2) and l be any integer with D(Q_n; x, y)≤l≤2ⁿ-1.If l-D(Q_n; x, y) is an even number, then there is an xy-path of length l in Q_n.

Let F be a set of faulty vertices in Q_n(d).

Lemma   3      For any subset F of V(Q₂(d))(d≥4, d is an even number) with |F|≤1, every edge of Q₂(d)-F lies on a fault-free k-cycle, k=4, 6, …, d²-2|F|.

Proof      In this article, the operation is modulo d.By corollary 1, we only consider |F|=1.Since Q₂(d) is vertex-transitive^[3], without loss of generality, we may assume that the faulty vertex is w=00.Let e=(u, v)=(x₁^*x₂^*, x₁^*x₂^**) be a fault-free edge of Q₂(d).We may assume that x₁^*≠0(x₁^*=0 is similar), (x₁^*x₂^*, x₁^*(x₂^*+1), …, x₁^*(x₂^*+2i), x₁^*x₂^**, x₁^*x₂^*) (i=1, 2, …, $ \frac{{d - 2}}{2}$;If x₂^*+j=x₂^**, j=1, 2, …, 2i, x₂^*+j is replaced by x₂^*+2i+1 is a (2i+2)-cycle and contains the edge e.

(x₁^*x₂^*, x₁^*(x₂^*+1), …, x₁^*(x₂^*+d-2), x₁^*(x₂^*+d-1), …, (x₁^*+k)(x₂^*+k×(d-1)), (x₁^*+k)(x₂^*+k×(d-1)+1), …, (x₁^*+k)(x₂^*+k×(d-1)+2i), (x₁^*+k)x₂^*, x₁^*x₂^**, x₁^*x₂^*)(k=1, 2, …, d-2;i=0, 1, …, $ \frac{{d - 2}}{2}$;If x₁^*+k=0, x₁^*+k is replaced by x₁^*+k+1.If x₂^**=(x₂^*+k×(d-1)+j) mod d, j=1, 2, …, 2i, x₂^*+k×(d-1)+j is replaced by x₂^*+k×(d-1)+2i+1) is a (k×d+2i+2)-cycle and contains the edge e.

We may assume that x₂^**≠0(x₂^**=0 similar), (x₁^*x₂^*, x₁^*(x₂^*+1), …, x₁^*(x₂^*+d-2), x₁^*(x₂^*+d-1), (x₁^*+1)(x₂^*+d-1), (x₁^*+1)(x₂^*+d), …, (x₁^*+1)(x₂^*+2×(d-1)), …, (x₁^*+d-2)(x₂^*+(d-2)(d-1)), (x₁^*+d-2)(x₂^*+(d-2)(d-1)+1), …, (x₁^*+d-2)(x₂^*+(d-1)(d-1)), 0(x₂^*+(d-1)(d-1)), 0(x₂^*+(d-1)(d-1)+1), …, 0(x₂^*+(d-1)(d-1)+2i), 0x₂^**, x₁^*x₂^**, x₁^*x₂^*), (i=0, 1, …, $ \frac{{d - 2}}{2}$;If 0=(x₂^*+(d-1)×(d-1)+j) mod d, j=1, 2, …, 2i, x₂^*+(d-1)×(d-1)+j is replaced by x₂^*+(d-1)×(d-1)+2i+1) is a ((d-1)×d+2i+2) and contains the edge e.

Lemma 4         For any subset F of V(Q₃(d))(d≥2, d is an even number) with |F|≤1, every edge of Q₃(d)-F lies on a fault-free k-cycle, k=4, 6, …, d³-2|F|.

Proof      By Corollary 1, we only consider |F|=1.Since Q₃(d) is vertex-transitive^[3], without loss of generality, we may assume that the faulty vertex is w=000.Let e=(u, v) be a fault-free edge of Q₃(d).By Lemma 2, Q₃(d) can be partitioned into dQ₂(d), denoted by Q₂ⁱ(d), 0≤i≤d-1;e∈Q_n-1^m(d)(m∈{1, 2, …, d-1}).Without loss of generality, we may assume that Q₃(d) is partitioned along dimension j(j∈{1, 2, 3}) into dQ₂(d), e∈Q₂¹(d) (If e∉Q₂¹(d) is similar).By Corollary 1, there is a fault-free even k-cycle in Q₂¹(d) containing the edge e where 4≤k≤d².Thus, the cycle of every even length from 4 to d² containing the edge e in Q₃(d) can be found in Q₂¹(d).Let C₁^* be a fault-free even d²-cycle containing the edge e in Q₂¹(d).Because d²≥4, therefore, C₁^* has an edge (u₁, v₁), (u₁, v₁)≠e, the cycle C₁^* can be represented as (u₁, v₁, P₁[v₁, u₁], u₁) where e lies on the path P₁[v₁, u₁].

u₁^j(2)∈Q₂²(d), v₁^j(2)∈Q₂²(d), h(u₁, v₁)=1, h(u₁, u₁^j(2))=1, h(v₁, v₁^j(2))=1, h(u₁^j(2), v₁^j(2))=1.By Corollary 1, there are even cycles with lengths from 4 to d² inclusive in Q₂²(d) that each cycle contains the edge (u₁^j(2), v₁^j(2)).Let C_l2=(v₁^j(2), u₁^j(2), P₂[u₁^j(2), v₁^j(2)], v₁^j(2)) be an even l₂-cycle containing the edge (u₁^j(2), v₁^j(2)) in Q₂²(d) where 4≤l₂≤d².Merging the two cycles C₁^* and C_l2 as well as the two edge (u₁, u₁^j(2)) and (v₁, v₁^j(2)), we can construct a fault-free even cycle C₁₂=(v₁, P₁[v₁, u₁], u₁, u₁^j(2), P₂[u₁^j(2), v₁^j(2)], v₁^j(2), v₁) which contains e.Obviously, l(C₁₂)=l(P₁[v₁, u₁])+l(P₂[u₁^j(2), v₁^j(2)])+2 where l(P₁[v₁, u₁])=d²-1 and l(P₂[u₁^j(2), v₁^j(2)])=1, 3, …, d²-1.Therefore, C₁₂ is an even cycle of length from d²+2 to 2d² and contains the edge e.

Let C_12…i^*(i=2, 3, …, d-2) be a fault-free even i×d²-cycle containing the edge e.C_12…i^* has an edge (u_i, v_i), (u_i, v_i)∉{e, (u₁, v₁), …, (u_i-1, v_i-1)}, the cycle C_12…i^* can be represented as (u_i, v_i, P_12…i[v_i, u_i], u_i) where e lies on the path P_12…i[v_i, u_i].u_i^j(i+1)∈Q₂ⁱ⁺¹(d), v_i^j(i+1)∈Q₂ⁱ⁺¹(d), h(u_i, v_i)=1, h(u_i, u_i^j(i+1))=1, h(v_i, v_i^j(i+1))=1, h(u_i^j(i+1), v_i^j(i+1))=1.By Corollary 1, there are even cycles with lengths from 4 to d² inclusive in Q₂ⁱ⁺¹(d) that each cycle contains the edge (u_i^j(i+1), v_i^j(i+1)).Let C_li+1=(v_i^j(i+1), u_i^j(i+1), P_i+1[u_i^j(i+1), v_i^j(i+1)], v_i^j(i+1)) be an even l_i+1-cycle containing the edge (u_i^j(i+1), v_i^j(i+1)) in Q₂ⁱ⁺¹(d) where 4≤l_i+1≤d².Merging the two cycles C_12…i^* and C_li+1 as well as the two edge (u_i, u_i^J(i+1)) and (v_i, v_i^J(i+1)), we can construct a fault-free even cycle C_12…(i+1)=(v_i, P_12…i[v_i, u_i], u_i, u_i^j(i+1), P_i+1[u_i^j(i+1), v_i^j(i+1)], v_i^j(i+1), v_i) which contains e.Obviously, l(C_12…(i+1))=l(P_12…i[v_i, u_i])+l(P_i+1[u_i^j(i+1), v_i^j(i+1)])+2 where l(P_12…i[v_i, u_i])=i×d²-1 and l(P_i+1[u_i^j(i+1), v_i^j(i+1)])=1, 3, …, d²-1.Therefore, C_12…(i+1) is an even cycle of length from i×d²+2 to (i+1)×d² and contains the edge e.

Let C_12…(d-1)^* be a fault-free even (d-1)×d²-cycle containing the edge e.C_12…(d-1)^* has an edge (u_d-1, v_d-1), (u_d-1, v_d-1)∉{e, (u₁, v₁), …, (u_d-2, v_d-2)}, the cycle C_12…(d-1)^* can be represented as (u_d-1, v_d-1, P_12…(d-1)[v_d-1, u_d-1], u_d-1) where e lies on the path P_12…(d-1)[v_d-1, u_d-1].u_d-1^j(0)∈Q₂⁰(d)-F, v_d-1^j(0)∈Q₂⁰(d)-F, h(u_d-1, v_d-1)=1, h(u_d-1, u_d-1^j(0))=1, h(v_d-1, v_d-1^j(0))=1, h(u_d-1^j(0), v_d-1^j(0))=1.By Lemma 3, there are even cycles with lengths from 4 to d²-2|F| inclusive in Q₂⁰(d)-F that each cycle contains the edge (u_d-1^j(0), v_d-1^j(0)).Let C_l0=(v_d-1^j(0), u_d-1^j(0), P₀[u_d-1^j(0), v_d-1^j(0)], v_d-1^j(0)) be an even l₀-cycle containing the edge (u_d-1^j(0), v_d-1^j(0)) in Q₂⁰(d)-F where 4≤l₀≤d²-2|F|.Merging the two cycles C_12…(d-1)^* and C_l0 as well as the two edge (u_d-1, u_d-1^J(0)) and (v_d-1, v_d-1^J(0)), we can construct a fault-free even cycle C_12…(d-1)0=(v_d-1, P_12…(d-1)[v_d-1, u_d-1], u_d-1, u_d-1^j(0), P₀[u_d-1^j(0), v_d-1^j(0)], v_d-1^j(d-1), v_d-1) which contains e.Obviously, l(C_12…(d-1)0)=l(P_12…(d-1)[v_d-1, u_d-1])+l(P₀[u_d-1^j(0), v_d-1^j(0)])+2 where l(P_12…(d-1)[v_d-1, u_d-1])=(d-1)×d²-1 and l(P₀[u_d-1^j(0), v_d-1^j(0)])=1, 3, …, d²-1-2|F|.Therefore, C_12…(d-1)0 is an even cycle of length from (d-1)×d²+2 to d³-2|F| and contains the edge e.

Similar to Lemma 4, we have

Theorem   2      Let n≥3 be an integer and Q_n(d)(d≥2, d is an even number) has exactly one faulty vertex.Then, every fault-free edge of Q_n(d) lies on a fault-free cycle of every even length from 4 to dⁿ-2.

Theorem   3      Let n≥3 be an integer.For any subset F of V(Q_n(d))(d≥2, d is an even number) with |F|=f_v≤n-2, every edge of Q_n(d)-F lies on a cycle of every even length from 4 to dⁿ-2f_v.

Proof      We prove this theorem by induction on n.By Lemma 4, Theorem 3 holds for n=3.Assuming that the theorem is true for every integer k(3≤k≤n).Let F be a subset of V(Q_k+1(d)) and |F|=f_v.By Corollary 1 and Theorem 2, Theorem 3 holds for f_v≤1.Thus, we only consider the case of 2≤f_v≤n-2.

Let w and z be two distinct faulty vertices.By Lemma 1, Q_k+1(d) can be partitioned along dimension j(j∈{1, 2, …, k+1} into d copies Q_k(d), denoted by Q_kⁱ(d)(i=0, 1, 2, …, d-1), w∈Q_k^l(d), z∈Q_k^m(d)(l, m∈{0, 1, 2, …, d-1}, l≠m).Let f_i=|F∩V(Q_kⁱ(d))|.i=0, 1, 2, …, d-1, i.e., f_v=∑ d-1 i=0 f_i.Therefore, f_i≤k-2, i=0, 1, 2, …, d-1.Let e=(u, v) be a fault-free edge of Q_k+1(d)-F.In order to prove this theorem, we establish every even l-cycle containing e where 4≤l≤d^k+1-2f_v.

Case   1: e∈E(Q_k⁰(d))∪E(Q_k¹(d))∪…∪E(Q_k^d-1(d)), i.e., e lies on Q_kⁱ(d)(i=0, 1, 2, …, d-1).We only consider that e∈E(Q_k⁰(d))(e∉E(Q_k⁰(d)) is similar).

Since f₀≤k-2, by induction hypothesis, there is a fault-free even l₀-cycle in Q_k⁰(d) containing the edge e where 4≤l₀≤d^k-2f₀.Thus, the cycle of every even length from 4 to d^k-2f₀ containing the edge e in Q_k+1(d) can be found in Q_k⁰(d).Let C_l0^* be a fault-free even l₀^*-cycle containing the edge e in Q_k⁰(d) where l₀^*=d^k-2f₀.One can observe that there are at least $\frac{1}{2} $ ×d^k-f₀-1 disjoint edges such that each of them differs with e in the cycle C_l0^*.Since k≥3 and $ \sum\limits_{i = 0}^{k + 1} $ f_i≤k-1, $\frac{1}{2} $ ×d^k-f₀-1> $ \sum\limits_{i = 0}^{k + 1} $ f_i.Therefore, C_l0^* has an edge (u₀, v₀), (u₀, v₀)≠e, u₀^j(m) is a fault-free vertex in Q_k^m(d), v₀^j(m) is a fault-free vertex in Q_k^m(d)(m∈{1, 2, …, d-1}, h(u₀, u₀^j(m))=1, h(v₀, v₀^j(m))=1.We may assume that m=1 (m≠1 is similar), i.e., u₀^j(1) is a fault-free vertex in Q_k¹(d), v₀^j(1) is a fault-free vertex in Q_k¹(d).The cycle C_l0^* can be represented as (u₀, v₀, P₀[v₀, u₀], u₀) where e lies on the path P₀[v₀, u₀].

Since f₁≤k-2, by induction hypothesis, there are even cycles with lengths from 4 to d^k-2f₁ in Q_k¹(d) that each cycle contains the edge (u₀^j(1), v₀^j(1)), Let C_l1=(v₀^j(1), u₀^j(1), P₁[u₀^j(1), v₀^j(1)], v₀^j(1)) be an even l₁-cycle containing the edge (u₀^j(1), v₀^j(1)) in Q_k¹(d) where 4≤l₁≤d^k-2f₁.Merging the two cycles C_l0^* and C_l1 as well as the two edges (u₀, u₀^j(1)) and (v₀, v₀^j(1)), we can construct a fault-free even cycle C₀₁=(v₀, P₀[v₀, u₀], u₀, u₀^j(1), P₁[u₀^j(1), v₀^j(1)], v₀^j(1), v₀) which contains e.Obviously, l(C₀₁)=l(P₀[v₀, u₀])+l(P₁[u₀^j(1), v₀^j(1)])+2 where l(C₀₁)=d^k-2f₀-1, and l(P₁[u₀^j(1), v₀^j(1)])=1, 3, …, d^k-2f₁-1.Therefore, the cycle C₀₁ is of length from d^k-2f₀+2 to 2×d^k-2(f₀+f₁) and contains the edge e.

Let C_012…i^*(i=1, 2, …, d-2) be a fault-free even ((i+1)×d^k-2 $ \sum\limits_{a = 0}^i $f_a)-cycle containing the edge e.One can observe that there are at least $\frac{1}{2} $ ×(i+1)d^k-$ \sum\limits_{a = 0}^i $f_a-1 disjoint edges such that each of them differs with e in the cycle C_012…i^*.Since k≥3 and $ \sum\limits_{a = 0}^{k + 1} $ f_a≤k-1, $\frac{1}{2} $ ×(i+1)d^k-$ \sum\limits_{a = 0}^i $f_a-i>∑$ \sum\limits_{a = i+1}^{k + 1} $ f_a.Therefore, C_012…i^* has an edge (u_i, v_i), (u_i, v_i)∈{e, (u₁, v₁), …, (u_i-1, v_i-1)}, u_i^j(m) is a fault-free vertex in Q_k^m(d), v_i^j(m) is a fault-free vertex in Q_k^m(d)(m∈{i+1, i+2, …, d-1}), h(u_i, u_i^j(m))=1, h(v_i, v_i^j(m))=1.We may assume that m=i+1(m≠i+1 is similar), i.e., u_i^j(i+1) is a fault-free vertex in Q_k^k+1(d), v_i^j(i+1) is a fault-free vertex in Q_k^k+1(d).The cycle C_012…i^* can be represented as (u_i, v_i, P_012…i[v_i, u_i], u_i) where e lies on the path P_012…i[v_i, u_i].

Since f_i+1≤k-2, by induction hypothesis, there are even cycles with lengths from 4 to d^k-2f_i+1 in Q_kⁱ⁺¹(d) that each cycle contains the edge (u_i^j(i+1), v_i^j(i+1)).Let C_li+1=(v_i^j(i+1), u_i^j(i+1), P_i+1[u_i^j(i+1), v_i^j(i+1)], v_i^j(i+1)) be an even l_i+1-cycle containing the edge (u_i^j(i+1), v_i^j(i+1)) in Q_kⁱ⁺¹(d) where 4≤l_i+1≤d^k-2f_i+1.Merging the two cycles C_012…i^* and C_li+1 as well as the two edges (u_i, u_i^j(i+1)) and (v_i, v_i^j(i+1)), we can construct a fault-free even cycle C_01…i(i+1)=(v_i, P_01…i[v_i, u_i], u_i, u_i^j(i+1), P_i+1[u_i^j(i+1), v_i^j(i+1)], v_i^j(i+1), v_i) which contains e.Obviously, l(C_01…i(i+1))=l(P_01…i[v_i, u_i])+l(P_i+1[u_i^j(i+1), v_i^j(i+1)])+2 where l(P_01…i[v_i, u_i])=(i+1)×d^k-2 $ \sum\limits_{a = 0}^i $f_a-1, and l(P_i+1[u_i^j(i+1), v_i^j(i+1)])=1, 3, …, d^k-2f_i+1-1.Therefore, the cycle C_01…i(i+1) is of length from (i+1)×d^k-2 $ \sum\limits_{a = 0}^i $ f_a+2 to (i+2)×d^k-2 $ \sum\limits_{a = 0}^{i+1} $ f_a and contains the edge e.

Case   2: e∉E(Q_k⁰(d))∪E(Q_k¹(d))∪…∪E(Q_k^d-1(d)), i.e., u∈Q_k^l(d)(l∈{0, 1, …, d-1}), v∈Q_k^m(d)(m∈{0, 1, …, d-1}), l≠m, e is an edge of dimension j and v=u^j(a)(j∈{1, 2, …, k+1}, a∈{0, 1, …, d-1}).

We assume that u∈Q_k⁰(d) and v∈Q_k¹(d) (If u∉Q_k⁰(d) or v∉Q_k¹(d) is similar).Since f_v≤(k+1)-2=k-1, there is an integer i(i∈{1, 2, …, k+1}), i≠j, such that u^i(a) and v^i(a)(a∈{0, 1, …, d-1}) are fault-free.Thus, (u, u^i(a), v^i(a), v, u) is a fault-free 4-cycle containing the edge e.Noting that u and u^i(a) (respectively, v and v^i(a)) are adjacent in Q_k⁰(d) (respectively, Q_k¹(d)).Since f₀≤k-2 and f₁≤k-2, by induction hypothesis, there is an even l₀-cycle in Q_k⁰(d) containing the edge (u, u^i(a)) such as C_l0=(u, u^i(a), P₀[u^i(a), u], u) and there is an even l₁-cycle in Q_k¹(d) containing the edge (v, v^i(a)) such as C_l1=(v^i(a), v, P₁[v, v^i(a)], v^i(a)) where 4≤l₀≤d^k-2f₀ and 4≤l₁≤d^k-2f₁.Combining the 4-cycle (u, u^i(a), v^i(a), v, u) and a 4-cycle containing (u, u^i(a)) in Q_k⁰(d), the desired 6-cycle can be obtained.Merging the two cycles C_l0 and C_l1 as well as the two edges (u, v) and (u^i(a), v^i(a)), we can construct a fault-free even cycle C₀₁=(u, v, P₁[v, v^i(a)], v^i(a), u^i(a), P₀[u^i(a), u], u) which contains e.Obviously, l(C₀₁)=l(P₁[v, v^i(a)])+l(P₀[u^i(a), u])+2 where l(P₀[u^i(a), u])=3, 5, …, d^k-2f₀-1 and l(P₁[v, v^i(a)])=3, 5, …, d^k-2f₁-1.This implies that 8≤l(C₀₁)≤2×d^k-2(f₀+f₁), l(C₀₁) is even and C₀₁ contains the edge e.

Let C_012…i^*(i=1, 2, …, d-2) be a fault-free even ((i+1)×d^k-2 $ \sum\limits_{a = 0}^i $ f_a)-cycle containing the edge e.Similar to Case 1, we can construct a fault-free even cycle C_01…i(i+1)=(v_i, P_01…i[v_i, u_i], u_i, u_i^j(i+1), P_i+1[u_i^j(i+1), v_i^j(i+1)], v_i^j(i+1), v_i) which contains e.The cycle C_01…i(i+1) is of length from (i+1)×d^k-2 $ \sum\limits_{a = 0}^i $ f_a+2 to (i+2)×d^k-2 $ \sum\limits_{a = 0}^i $ f_a and contains the edge e.

Since |F|≤n-2 and the degree of any vertex of Q_n(d) is n(d-1), any fault-free vertex of Q_n(d) has at least n(d-2)+2 fault-free neighbors.Thus, every fault-free vertex can be incident by a fault-free edge.Therefore, we have

Corollary   3      Let n≥3 be an integer.For any subset F of V(Q_n(d))(d≥2, d is an even number) with |F|≤n-2, every vertex of Q_n(d)-F lies on a fault-free cycle of every even length from 4 to dⁿ-2|F|.

Applying Theorem 3.If d=2, we have

Corollary   4^[2]      Assuming that n≥3.For any subset F of V(Q_n(d)) with |F|=f_v≤n-2, every edge of Q_n(d)-F lies on a cycle of every even length from 4 to 2ⁿ-2f_v.

Applying Corollary 4.We have

Corollary   5^[2]      Let n≥3 be an integer.For any subset F of V(Q_n(d)) with |F|≤n-2, every vertex of Q_n-F lies on a fault-free cycle of every even length from 4 to 2ⁿ-2|F|.

3 d is an odd number

Theorem   4      Let x and y be any two vertices in Q_n(d)(n≥2) and l be any integer with D(Q_n(d); x, y)≤l≤dⁿ-1.If d is an odd number, l-D(Q_n(d); x, y) is an even number, then there is an xy-path of length l in Q_n(d).Moreover, if D(Q_n(d); x, y)=1, there is an xy-path of length l=dⁿ-1 in Q_n(d).

Proof     Let D(Q_n(d); x, y)=m.The proof is based on the recursive structure of Q_n(d) by induction on n≥2.

When n=2, if D(Q_n(d); x, y)=1.By the vertex-transitivity of Q₂(d)^[3], without loss of generality, we can assume x=00, y=01.

x=00→01=y, x=00→02→03→01=y, x=00→02→03→04→05→01=y, …, x=00→02→03→04→05→…→0(d-3)→0(d-2)→01=y are the xy-path of length l=1, 3, 5, …, d-2 in Q₂(d).

x=00→10→12→02→03→04→05→…→0(d-3)→0(d-2)→01=y, x=00→10→20→22→12→02→03→04→05→…→0(d-3)→0(d-2)→01=y, ….

x=00→10→20→30→40→…→(d-2)0→(d-1)0→(d-1)2→(d-2)2→…→22→12→02→03→13→23→…→(d-2)3→(d-1)3→(d-1)4→(d-2)4→…→24→14→04→…→0(d-4)→1(d-4)→2(d-4)→…→(d-2)(d-4)→(d-1)(d-4)→(d-1)(d-3)→(d-2)(d-3)→…→2(d-3)→1(d-3)→0(d-3)→0(d-2)→1(d-2)→2(d-2)→…→(d-2)(d-2)→(d-1)(d-2)→(d-1)1→(d-2)1→…→21→11→01=y, ….

x=00→10→20→30→40→…→(d-2)0→(d-1)0→(d-1)2→(d-2)2→…→22→12→02→03→13→23→…→(d-2)3→(d-1)3→(d-1)4→(d-2)4→…→24→14→04→…→0(d-4)→1(d-4)→2(d-4)→…→(d-2)(d-4)→(d-1)(d-4)→(d-1)(d-3)→(d-2)(d-3)→…→2(d-3)→1(d-3)→0(d-3)→0(d-2)→1(d-2)→2(d-2)→…→(d-2)(d-2)→(d-1)(d-2)→(d-1)1→(d-1)(d-1)→(d-2)(d-1)→(d-2)1→(d-3)1→(d-3)(d-1)→(d-4)(d-1)→(d-4)1→…→21→2(d-1)→1(d-1)→11→01=y are the xy-path of length l=d, d+2, …, d²-d-1, …, d²-2 in Q₂(d).

x=00→10→20→30→40→…→(d-2)0→(d-1)0→(d-1)2→(d-2)2→…→22→12→02→03→13→23→…→(d-2)3→(d-1)3→(d-1)4→(d-2)4→…→24→14→04→…→0(d-4)→1(d-4)→2(d-4)→…→(d-2)(d-4)→(d-1)(d-4)→(d-1)(d-3)→(d-2)(d-3)→…→2(d-3)→1(d-3)→0(d-3)→0(d-2)→1(d-2)→2(d-2)→…→(d-2)(d-2)→(d-1)(d-2)→(d-1)1→(d-1)(d-1)→(d-2)(d-1)→(d-2)1→(d-3)1→(d-3)(d-1)→(d-4)(d-1)→(d-4)1→…→21→2(d-1)→0(d-1)→1(d-1)→11→01=y is the xy-path of length l=d²-1 in Q₂(d).

The rest of the inductive proof are similar to Theorem 1.

Applying Theorem 4, we have

Corollary   6     For any n≥2, every edge of Q_n(d)(d≥3, d is an odd number) lies on a cycle of every even length from 4 to dⁿ-1.Moreover, every edge of Q_n(d) lies on a cycle of length dⁿ.

Similar to Lemma 3.We have

Lemma   5      For any subset F of V(Q₂(d))(d≥3, d is an odd number) with |F|≤1, every edge of Q₂(d)-F lies on a fault-free k-cycle, k=4, 6, …, d²-2|F|-1.Moreover, every edge of Q₂(d)-F lies on a fault-free (d²-2|F|)-cycle.

Similar to Lemma 4, applying Theorem 4 and Lemma 5.We have

Lemma   6      For any subset F of V(Q₃(d))(d≥3, d is an odd number) with |F|≤1, every edge of Q₃(d)-F lies on a fault-free k-cycle, k=4, 6, …, d³-2|F|-1.Moreover, every edge of Q₃(d)-F lies on a fault-free (d³-2|F|)-cycle.

Similar to Lemma 6, we have

Theorem   5     Let n≥3 be an integer and Q_n(d)(d≥3, d is an odd number) has exactly one faulty vertex.Then, every fault-free edge of Q_n(d) lies on a fault-free cycle of every even length from 4 to dⁿ-3.Moreover, every fault-free edge of Q_n(d) lies on a fault-free cycle of length dⁿ-2.

Theorem   6      Let n≥3 be an integer.For any subset F of V(Q_n(d))(d≥3, d is an odd number) with |F|=f_v≤n-2, every edge of Q_n(d)-F lies on a cycle of every even length from 4 to dⁿ-2f_v-1.Moreover, every edge of Q_n(d)-F lies on a cycle of length dⁿ-2f_v.

Proof   We prove this theorem by induction on n.By Lemma 6, Theorem 6 holds for n=3.Assuming that the theorem is true for every integer k(3≤k≤n).Let F be a subset of V(Q_k+1(d)) and |F|=f_v.By Corollary 6 and Theorem 5, Theorem 6 holds for f_v≤1.Thus, we only consider the case of 2≤f_v≤n-2.

Let w and z be two distinct faulty vertices.By Lemma 1, Q_k+1(d) can be partitioned along dimension j(j∈{1, 2, …, k+1}) into d copies Q_k(d), denoted by Q_kⁱ(d)(i=0, 1, …, d-1), w∈Q_k^l(d), z∈Q_k^m(d)(l, m∈{0, 1, 2, …, d-1}, l≠m).Let f_i=|F∩V(Q_kⁱ(d))|, i=0, 1, 2, …d-1, i.e., f_v=$ \sum\limits_{i = 0}^{d-1} $ f_i.Therefore, f_i≤k-2, i=0, 1, 2, …, d-1.Let e=(u, v) be a fault-free edge of Q_k+1(d)-F.In order to prove this theorem, we establish every even l-cycle containing e where 4≤l≤d^k+1-2f_v-1, and a (d^k+1-2f_v)-cycle containing e.

Case   1: e∈E(Q_k⁰(d))∪E(Q_k¹(d))∪…∪E(Q_k^d-1(d)), i.e., e lies on Q_kⁱ(d)(i∈{0, 1, 2, …, d-1}).We only consider that e∈E(Q_k⁰(d))(e∉E(Q_k⁰(d)) is similar).

Since f₀≤k-2, by induction hypothesis, there is a fault-free even l₀-cycle in Q_k⁰(d) containing the edge e where 4≤l₀≤d^k-2f₀-1, and there exists a fault-free (d^k-2f₀)-cycle in Q_k⁰(d) containing the edge e.Thus, the cycle of every even length from 4 to d^k-2f₀-1 containing the edge e in Q_k+1(d) can be found in Q_k⁰(d).Let C_l0^*(C_l0^*′) be a fault-free even l₀^*-cycle (l₀^*′-cycle) containing the edge e in Q_k⁰(d) where l₀^*=d^k-2f₀-1(l₀^*′=d^k-2f₀).One can observe that there are at least 1 2 ×(d^k-1)-f₀-1 disjoint edges such that each of them differs with e in the cycle C_l0^*(C_l0^*′).Since k≥3 and $ \sum\limits_{i = 0}^{k+1} $ f_i≤k-1, 1 2 ×(d^k-1)-f₀-1>$ \sum\limits_{i = 1}^{k+1} $ f_i.Therefore, C_l0^*(C_l0^*′) has an edge (u₀, v₀), (u₀, v₀)≠e, u₀^j(m) is a fault-free vertex in Q_k^m(d), v₀^j(m) is a fault-free vertex in Q_k^m(d)(m∈{1, 2, …, d-1), h(u₀, u₀^j(m))=1, h(v₀, v₀^j(m))=1.We may assume that m=1 (m≠1 is similar), i.e., u₀^j(1) is a fault-free vertex in Q_k¹(d), v₀^j(1) is a fault-free vertex in Q_k¹(d).The cycle C_l0^*(C_l0^*′) can be represented as (u₀, v₀, P₀[v₀, u₀], u₀) where e lies on the path P₀[v₀, u₀].

Since f₁≤k-2, by induction hypothesis, there are even cycles with lengths from 4 to d^k-2f₁-1 in Q_k¹(d) that each cycle contains the edge (u₀^j(1), v₀^j(1)), and there is a cycle of length d^k-2f₁ in Q_k¹(d) that the cycle contains the edge (u₀^j(1), v₀^j(1)).Let C_l1=(v₀^j(1), u₀^j(1), P₁[u₀^j(1), v₀^j(1)], v₀^j(1)) be an even l₁-cycle containing the edge (u₀^j(1), v₀^j(1)) in Q_k¹(d) where 4≤l₁≤d^k-2f₁-1, C_l1^′=(v₀^j(1), u₀^j(1), P₁[u₀^j(1), v₀^j(1)], v₀^j(1)) be a (d^k-2f₁)-cycle containing the edge (u₀^j(1), v₀^j(1)) in Q_k¹(d).Merging the two cycles C_l0^* and C_l1 as well as the two edges (u₀, u₀^j(1)) and (v₀, v₀^j(1)), we can construct a fault-free even cycle C₀₁=(v₀, P₀[v₀, u₀], u₀, u₀^j(1), P₁[u₀^j(1), v₀^j(1)], v₀^j(1), v₀) which contains e.Obviously, l(C₀₁)=l(P₀[v₀, u₀])+l(P₁[u₀^j(1), v₀^j(1)])+2 where l(P₀[v₀, u₀])=d^k-2f₀-2, and l(P₁[u₀^j(1), v₀^j(1)])=1, 3, …, d^k-2f₁-1.Therefore, the cycle C₀₁ is of length from d^k-2f₀+1 to 2×d^k-2(f₀+f₁)-2 and contains the edge e.Merging the two cycles C_l0^*′ and C_l1^′ as well as the two edges (u₀, u₀^j(1)) and (v₀, v₀^j(1)), we can construct a fault-free even cycle C₀₁^′=(v₀, P₀[v₀, u₀], u₀, u₀^j(1), P₁[u₀^j(1), v₀^j(1)], v₀^j(1), v₀) which contains e.Obviously, l(C₀₁^′)=l(P₀[v₀, u₀])+l(P₁[u₀^j(1), v₀^j(1)])+2 where l(P₀[v₀, u₀])=d^k-2f₀-1 and l(P₁[u₀^j(1), v₀^j(1)])=d^k-2f₁-1.Therefore, the cycle C₀₁^′ is (2×d^k-2(f₀+f₁))-cycle and contains the edge e.

Let C_{012, …i}^*(i=1, 3, …, d-4, d-2) be a fault-free even ((i+1)×d^k-2$ \sum\limits_{a = 0}^i $ f_a)-cycle containing the edge e.One can observe that there are at least 1 2 ×(i+1)d^k-$ \sum\limits_{a = 0}^i $ f_a-1 disjoint edges such that each of them differs with e in the cycle C_{012, …i}^*.Since k≥3 and $ \sum\limits_{a = 0}^{k+1} $ f_a≤k-1, $ \frac{1}{2}$ ×(i+1)d^k-$ \sum\limits_{a = 0}^i $ f_a-1>$ \sum\limits_{a = i+1}^{k+1} $ f_a.Therefore, C_{012, …i}^* has an edge (u_i, v_i), (u_i, v_i)∉{e, (u₁, v₁), …, (u_i-1, v_i-1)}, u_i^j(m) is a fault-free vertex in Q_k^m(d), v_i^j(m) is a fault-free vertex in Q_k^m(d)(m∈{i+1, i+2, …, d-1}), h(u_i, u_i^j(m))=1, h(v_i, v_i^j(m))=1.We may assume that m=i+1 (m≠i+1 is similar), i.e., u_i^j(i+1) is a fault-free vertex in Q_kⁱ⁺¹(d), v_i^j(i+1) is a fault-free vertex in Q_kⁱ⁺¹(d).The cycle C_{012, …i}^* can be represented as (u_i, v_i, P_012…i[v_i, u_i], u_i) where e lies on the P_012…i[v_i, u_i].

Since f_i+1≤k-2, by induction hypothesis, there are even cycles with lengths from 4 to d^k-2f_i+1-1 in Q_kⁱ⁺¹(d)that each cycle contains the edge (u_i^j(i+1), v_i^j(i+1)), and there is a (d^k-2f_i+11)-cycle in Q_kⁱ⁺¹(d) that the cycle contains the edge (u_i^j(i+1), v_i^j(i+1)).Let C_li+1=(v_i^j(i+1), u_i^j(i+1), P_i+1[u_i^j(i+1), v_i^j(i+1)], v_i^j(i+1)) be an even l_i+1-cycle containing the edge (u_i^j(i+1), v_i^j(i+1)) in Q_kⁱ⁺¹(d) where 4≤l_i+1≤d^k-2f_i+1-1, C_l^′i+1=(v_i^j(i+1), u_i^j(i+1), P_i+1[u_i^j(i+1), v_i^j(i+1)], v_i^j(i+1)) be a (d^k-2f_i+11)-cycle containing the edge (u_i^j(i+1), v_i^j(i+1)) in Q_kⁱ⁺¹(d).Merging the two cycles C_{012, …i}^* and C_li+1as well as the two edges (u_i, u_i^j(i+1)) and (v_i, v_i^j(i+1)), we can construct a fault-free even cycle C_01…i(i+1)=(v_i, P_01…i[v_i, u_i], u_i, u_i^j(i+1), P_i+1[u_i^j(i+1), v_i^j(i+1)], v_i^j(i+1), v_i) which contains e.Obviously, l(C_01…i(i+1))=l(P_01…i[v_i, u_i])+l(P_i+1[u_i^j(i+1), v_i^j(i+1)]+2 where l(P_01…i[v_i, u_i])=(i+1)×d^k-2$ \sum\limits_{a = 0}^i $ f_a-1, and l(P_i+1[u_i^j(i+1), v_i^j(i+1)])=1, 3, …, d^k-2f_i+1-2.Therefore, the cycle C_01…i(i+1) is of length from (i+1)×d^k-2$ \sum\limits_{a = 0}^i $ f_a+2 to (i+2)×d^k-2$ \sum\limits_{a = 0}^i $ f_a-1 and contains the edge e.Merging the two cycles C_{012, …i}^* and C_l^′i+1 as well as the two edges (u_i, u_i^j(i+1)) and (v_i, v_i^j(i+1)), we can construct a fault-free even cycle C_01…i(i+1)^′=(v_i, P_01…i[v_i, u_i], u_i, u_i^j(i+1), P_i+1[u_i^j(i+1), v_i^j(i+1)], v_i^j(i+1), v_i) which contains e.Obviously,

l(C_01…i(i+1)^′)=l(P_01…i[v_i, u_i])+l(P_i+1[u_i^j(i+1), v_i^j(i+1)])+2 where l(P_01…i[v_i, u_i])=(i+1)×d^k-2$ \sum\limits_{a = 0}^i $ f_a-1 and l(P_i+1[u_i^j(i+1), v_i^j(i+1)])=d^k-2f_i+1-1.Therefore, the cycle C_01…i(i+1)^′ is ((i+2)×d^k-2$ \sum\limits_{a = 0}^i $ f_a)-cycle and contains the edge e.

Let C_{012, …i}^*(i=2, 4, …, d-5, d-3) be a fault-free even ((i+1)×d^k-2$ \sum\limits_{a = 0}^i $ f_a-1)-cycle containing the edge e, C_{012, …i}^*′ be a fault-free ((i+1)×d^k-2$ \sum\limits_{a = 0}^i $ f_a)-cycle containing the edge e.One can observe that there are at least 1 2 ×[(i+1)d^k-1]-$ \sum\limits_{a = 0}^i $ f_a-1 disjoint edges such that each of them differs with e in the cycle C_{012, …i}^*.Since k≥3 and $ \sum\limits_{a = 0}^{k+1} $ f_a≤k-1, 1 2 ×[(i+1)d^k-1]-$ \sum\limits_{a = 0}^i $ f_a-i>$ \sum\limits_{a = i+1}^{k+1} $ f_a.Therefore, C_{012, …i}^*(C_{012, …i}^*′) has an edge (u_i, v_i), (u_i, v_i)∉{e, (u₁, v₁), …, (u_i-1, v_i-1)}, u_i^j(m) is a fault-free vertex in Q_k^m(d), v_i^j(m) is a fault-free vertex in Q_k^m(d)(m∈{i+1, i+2, …, d-1}), h(u_i, u_i^j(m))=1, h(v_i, v_i^j(m))=1.We may assume that m=i+1 (m≠i+1 is similar), i.e., u_i^j(i+1) is a fault-free vertex in Q_kⁱ⁺¹(d), v_i^j(i+1) is a fault-free vertex in Q_kⁱ⁺¹(d).The cycle C_{012, …i}^*(C_{012, …i}^*′) can be represented as (u_i, v_i, P_012…i[v_i, u_i], u_i) where e lies on the P_012…i[v_i, u_i].

Since f_i+1≤k-2, by induction hypothesis, there are even cycles with lengths from 4 to d^k-2f_i+1-1 in Q_kⁱ⁺¹(d)that each cycle contains the edge (u_i^j(i+1), v_i^j(i+1)), and there is a (d^k-2f_i+11)-cycle in Q_kⁱ⁺¹(d) that the cycle contains the edge (u_i^j(i+1), v_i^j(i+1)).Let C_li+1=(v_i^j(i+1), u_i^j(i+1), P_i+1[u_i^j(i+1), v_i^j(i+1)], v_i^j(i+1)) be an even l_i+1-cycle containing the edge (u_i^j(i+1), v_i^j(i+1)) in Q_kⁱ⁺¹(d) where 4≤l_i+1≤d^k-2f_i+1-1, C_l^′i+1=(v_i^j(i+1), u_i^j(i+1), P_i+1[u_i^j(i+1), v_i^j(i+1)], v_i^j(i+1)) be a (d^k-2f_i+1)-cycle containing the edge (u_i^j(i+1), v_i^j(i+1)) in Q_kⁱ⁺¹(d).Merging the two cycles C_{012, …i}^* and C_li+1as well as the two edges (u_i, u_i^j(i+1)) and (v_i, v_i^j(i+1)), we can construct a fault-free even cycle C_01…i(i+1)=(v_i, P_01…i[v_i, u_i], u_i, u_i^j(i+1), P_i+1[u_i^j(i+1), v_i^j(i+1)], v_i^j(i+1), v_i) which contains e.Obviously, l(C_01…i(i+1))=l(P_01…i[v_i, u_i])+l(P_i+1[u_i^j(i+1), v_i^j(i+1)]+2 where l(P_01…i[v_i, u_i])=(i+1)×d^k-2$ \sum\limits_{a = 0}^i $ f_a-2, and l(P_i+1[u_i^j(i+1), v_i^j(i+1)])=1, 3, …, d^k-2f_i+1-2.Therefore, the cycle C_01…i(i+1) is of length from (i+1)×d^k-2$ \sum\limits_{a = 0}^i $ f_a+1 to (i+2)×d^k-2$ \sum\limits_{a = 0}^{i+1} $ f_a-2 and contains the edge e.Merging the two cycles C_{012, …i}^*′ and C_l^′i+1 as well as the two edges (u_i, u_i^j(i+1)) and (v_i, v_i^j(i+1)), we can construct a fault-free even cycle C_01…i(i+1)^′=(v_i, P_01…i[v_i, u_i], u_i, u_i^j(i+1), P_i+1[u_i^j(i+1), v_i^j(i+1)], v_i^j(i+1), v_i) which contains e.Obviously, l(C_01…i(i+1)^′)=l(P_01…i[v_i, u_i])+l(P_i+1[u_i^j(i+1), v_i^j(i+1)])+2 where l(P_01…i[v_i, u_i])=(i+1)×d^k-2$ \sum\limits_{a = 0}^i $ f_a-1 and l(P_i+1[u_i^j(i+1), v_i^j(i+1)])=d^k-2f_i+1-1.Therefore, the cycle C_01…i(i+1)^′ is ((i+2)×d^k-2$ \sum\limits_{a = 0}^{i+1} $ f_a)-cycle and contains the edge e.

Case   2 : e∉E(Q_k⁰(d))∪E(Q_k¹(d))∪…∪E(Q_k^d-1(d)), i.e., u∈Q_k^l(d)(l∈{0, 1, …, d-1}), v∈Q_k^m(d)(m∈{0, 1, …, d-1}), l≠m, e is an edge of dimension j and v=u^j(a)(j∈{1, 2, …, k+1}, a∈{0, 1, …, d-1}).

The proof of Case 2 is similar to the proof of Case 2 of Theorem 3.

Applying Theorem 6, we have

Corollary   7      Let n≥3 be an integer.For any subset F of V(Q_n(d))(d≥3, d is an odd number) with |F|≤n-2, every vertex of Q_n(d)-F lies on a fault-free cycle of every even length from 4 to dⁿ-2|F|.Moreover, every vertex of Q_n(d)-F lies on a fault-free cycle of length dⁿ-2|F|.