PATHS AND CYCLES EMBEDDING ON FAULTY ENHANCED HYPERCUBE NETWORKS

Let Q_n,k (n ≥ 3, 1 ≤ k ≤ n?1) be an n-dimensional enhanced hypercube which is an attractive variant of the hypercube and can be obtained by adding some complementary edges, f_v and f_e be the numbers of faulty vertices and faulty edges, respectively. In this paper, we give three main results. First, a fault-free path Pu,v] of length at least 2ⁿ?2f_v?1 (respectively, 2ⁿ?2f_v?2) can be embedded on Q_n,k with f_v+f_e ≤ n?1 when d_Qn,k(u,v) is odd (respectively, d_Qn,k(u,v) is even). Secondly, an Q_n,k is (n?2) edge-fault-free hyper Hamiltonian-laceable when n (≥ 3) and k have the same parity. Lastly, a fault-free cycle of length at least 2ⁿ?2f_v can be embedded on Q_n,k with f_e ≤ n?1 and f_v+f_e ≤ 2n?4.