Embedding Hamiltonian Cycles into Folded Hypercubes with Faulty Links

It has been known that an n-dimensional hypercube (n-cube for short) can always embed a Hamiltonian cycle when the n-cube has no more than n-2 faulty links. In this paper, we study the link-fault tolerant embedding of a Hamiltonian cycle into the folded hypercube, which is a variant of the hypercube, obtained by adding a link to every pair of nodes with complementary addresses. We will show that a folded n-cube can tolerate up to n-1 faulty links when embedding a Hamiltonian cycle. We present an algorithm, FT_HAMIL, that finds a Hamiltonian cycle while avoiding any set of faulty links F provided that F≤n-1. An operation, called bit-flip, on links of hyper-cube is introduced. Simple yet elegant, bit-flip will be employed by FT_HAMIL as a basic operation to generate a new Hamiltonian cycle from an old one (that contains faulty links). It is worth pointing out that the algorithm is optimal in the sense that for a folded n-cube, n-1 is the maximum number for F that can be tolerated, F being an arbitrary set of faulty links.