On the mutually independent Hamiltonian cycles in faulty hypercubes ?
Two ordered Hamiltonian paths in the n-dimensional hypercube Qn are said to be independent if ith vertices of the paths are distinct for every 1?i?2n. Similarly, two s-starting Hamiltonian cycles are independent if the ith vertices of the cycle are distinct for every 2?i?2n. A set S of Hamiltonian paths (s-starting Hamiltonian cycles) are mutually independent if every two paths (cycles, respectively) from S are independent. We show that for n pairs of adjacent vertices wi and bi, there are n mutually independent Hamiltonian paths with endvertices wi, bi in Qn. We also show that Qn contains n?f fault-free mutually independent s-starting Hamiltonian cycles, for every set of f?n?2 faulty edges in Qn and every vertex s. This improves previously known results on the numbers of mutually independent Hamiltonian paths and cycles in the hypercube with faulty edges.
hamiltonian cycle hypercube hamiltonian path faulty edge interconnection network