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(n2n) 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.