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 P[u,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.