Paths and cycles embedding on faulty enhanced hypercube networks

Let Qn,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, fv and fe 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 2n−2fv−1 (respectively, 2n−2fv−2) can be embedded on Qn,k with fv+fe ≤ n−1 when dQn,k(u,v) is odd (respectively, dQn,k(u,v) is even). Secondly, an Qn,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 2n−2fv can be embedded on Qn,k with fe ≤ n−1 and fv+fe ≤ 2n−4.