Vertex-Fault-Tolerant Cycles Embedding on Enhanced Hypercube Networks

In this paper, we study the enhanced hypercube, an attractive variant of the hypercube and obtained by adding some complementary edges from a hypercube, and focus on cycles embedding on the enhanced hypercube with faulty vertices. Let Fv be the set of faulty vertices in the n-dimensional enhanced hypercube Qn,k (n ≥ 3, 1 ≤ k ≤ n − 1). When |Fv| = 2, we showed that Qn,k − Fv contains a fault-free cycle of every even length from 4 to 2n – 4 where n (n ≥ 3) and k have the same parity; and contains a fault-free cycle of every even length from 4 to 2n − 4, simultaneously, contains a cycle of every odd length from n − k + 2 to 2n − 3 where n (≥ 3) and k have the different parity. Furthermore, when |Fv| = fv ≤ n − 2, we prove that there exists the longest fault-free cycle, which is of even length 2n − 2fv whether n (n ≥ 3) and k have the same parity or not; and there exists the longest fault-free cycle, which is of odd length 2n − 2fv + 1 in Qn,k − Fv where n (≥ 3) and k have the different parity.