Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes

The n-dimensional hypercube network Qn is one of the most popular interconnection networks since it has simple structure and is easy to implement. The n-dimensional locally twisted cube LTQn, an important variation of the hypercube, has the same number of nodes and the same number of connections per node as Qn. One advantage of LTQn is that the diameter is only about half of the diameter of Qn. Recently, some interesting properties of LTQn have been investigated in the literature. The presence of edge-disjoint Hamiltonian cycles provides an advantage when implementing algorithms that require a ring structure by allowing message traffic to be spread evenly across the interconnection network. The existence of two edge-disjoint Hamiltonian cycles in locally twisted cubes has remained unknown. In this paper, we prove that the locally twisted cube LTQn with n⩾4 contains two edge-disjoint Hamiltonian cycles. Based on the proof of existence, we further provide an O(n2n)-linear time algorithm to construct two edge-disjoint Hamiltonian cycles in an n-dimensional locally twisted cube LTQn with n⩾4, where LTQn contains 2n nodes and n2n−1 edges.