Two Edge-Disjoint Hamiltonian Cycles in Shuffle-cubes

The n-dimensional shuffle-cube SQ<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</inf>, a variation of the hypercube Q<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</inf>, has the same number of vertices and the same number of edges as Q<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</inf>, but it has only about 1/4 of the diameter of Q<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</inf>. In the interconnection network, some efficient communication algorithms can be designed based on Hamiltonian cycles. In addition, two edge-disjoint Hamiltonian cycles also provide the edge-fault tolerant Hamiltonicity. In this paper, we show two edge-disjoint Hamiltonian cycles in SQ<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">6</inf>, and then provide two algorithms to construct these cycles. Finally, we give recursive constructions of two edge-disjoint Hamiltonian cycles in SQ<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</inf> for n ≥ 6.