Fault-free cycles passing through prescribed paths in hypercubes with faulty edges

AbstractAn n-dimensional hypercube, or n-cube, denoted by Qn, is well known as bipartite and one of the most efficient networks for parallel computation. In this work, we consider the problem of cycles passing through prescribed paths in an n-dimensional hypercube with faulty edges. We obtain the following result: For n≥3 and 2≤h<n, let F be a subset of E(Qn) with |F|<n−h. Then, every fault-free path P with length h lies on a fault-free cycle in Qn−F of every even length from d to 2n inclusive where d=2h if h>|F|+1 and d=2h+2 otherwise. The result is optimal