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 F_v be the set of faulty vertices in the n-dimensional enhanced hypercube Q_n,k (n ≥ 3, 1 ≤ k ≤ n ? 1). When |F_v| = 2, we showed that Q_n,k ? F_v contains a fault-free cycle of every even length from 4 to 2ⁿ – 4 where n (n ≥ 3) and k have the same parity; and contains a fault-free cycle of every even length from 4 to 2ⁿ ? 4, simultaneously, contains a cycle of every odd length from n ? k + 2 to 2ⁿ ? 3 where n (≥ 3) and k have the different parity. Furthermore, when |F_v| = f_v ≤ n ? 2, we prove that there exists the longest fault-free cycle, which is of even length 2ⁿ ? 2f_v 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 2ⁿ ? 2f_v + 1 in Q_n,k ? F_v where n (≥ 3) and k have the different parity.