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

An n-dimensional hypercube, or n-cube, denoted by Q(n) 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(Q(n)) with vertical bar F vertical bar < n - h. Then, every fault-free path P with length h lies on a fault-free cycle in Q(n) - F of every even length from d to 2(n) inclusive where d = 2h if h > vertical bar F vertical bar + 1 and d = 2h + 2 otherwise. The result is optimal. (C) 2008 Elsevier Ltd. All rights reserved.