Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes

摘要

The n-dimensional hypercube network Q_n is one of the most popular interconnection networks since it has simple structure and is easy to implement. The n-dimensional locally twisted cube LTQ_n, an important variation of the hypercube, has the same number of nodes and the same number of connections per node as Q_n. One advantage of LTQ_n is that the diameter is only about half of the diameter of Q_n. Recently, some interesting properties of LTQ_n 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 LTQ_n with n ≥ 4 contains two edge-disjoint Hamiltonian cycles. Based on the proof of existence, we further provide an O(n2~n)-linear time algorithm to construct two edge-disjoint Hamiltonian cycles in an n-dimensional locally twisted cube LTQ_n with n ≥ 4, where LTQ_n contains 2~n nodes and n2~(n-1) edges.