A Parallel Algorithm for Constructing Two Edge-disjoint Hamiltonian Cycles in Locally Twisted Cubes

The locally twisted cube LTQ
_n
is a variation of the hypercube Q
_n
, and the diameter of LTQ
_n
is only about half of the diameter of Q
_n
. For interconnection networks, some efficient communication algorithms can be designed based on the ring structure. In addition, two edge-disjoint Hamiltonian cycles also provide the edge-fault tolerant Hamiltonicity for the interconnection network. Hung [Theoretical Computer Science 412, 4747-4753, 2011] designed an O(n2
ⁿ
) time algorithm to construct two edge-disjoint Hamiltonian cycles in LTQ
_n
. In this paper, we provide parallel algorithms for each vertex in LTQ
_n
to determine which two edges were adopted in the first or second Hamiltonian cycles, respectively. By connecting these edges, we can construct two edge-disjoint Hamiltonian cycles in LTQ
_n
where n ≥ 4.