Mutually independent Hamiltonian cycles in dual-cubes

The hypercube family Q(n) is one of the most well-known interconnection networks in parallel computers. With Q(n) , dual-cube networks, denoted by DCn , was introduced and shown to be a (n+1)-regular, vertex symmetric graph with some fault-tolerant Hamiltonian properties. In addition, DCn's are shown to be superior to Q(n)'s in many aspects. In this article, we will prove that the n-dimensional dual-cube DCn contains n+1 mutually independent Hamiltonian cycles for n >= 2. More specifically, let upsilon(i) is an element of V(DC (n) ) for 0 <= i <= |V(DCn)|-1 and let (upsilon(0,) upsilon(1,.....,) upsilon broken vertical bar v(DCn)broken vertical bar-1, upsilon(0)) be a Hamiltonian cycle of DCn . We prove that DCn contains n+1 Hamiltonian cycles of the form (upsilon(0,) upsilon(k)(1), .....,upsilon(k)vertical bar v (DCn)vertical bar-1, upsilon(0)) for 0 <= k <= n, in which v(i)(k) not equal v(i)(k') whenever k not equal k'. The result is optimal since each vertex of DCn has only n+1 neighbors.