Constructing Two Edge-Disjoint Hamiltonian Cycles and Two-Equal Path Cover in Augmented Cubes

Abstract

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 augmented cube AQn, an important variation of the hypercube, possesses several embedding properties that hypercubes and other variations do not possess. The advantages of AQn are that the diameter is only about half of the diameter of Qn and it is node-symmetric. Recently, some interesting properties of AQn 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. A network G contains two-equal path cover and is called two-equal path coverable if for any two distinct pairs of nodes �µ s ,µ tand �υ s ,υ tof G, there exist two node-disjoint paths P and Q satisfying that (1) P joins µs and µt, and Q joins υs and υt, (2) |P | = |Q|, and (3) every node of G appears in P ∪ Q exactly once. In this paper, we first prove that the augmented cube AQn contains two edge- disjoint Hamiltonian cycles for n 3. We then prove that AQn, with n 2, is two-equal path coverable. Based on the proofs of existences, we further present linear time algorithms to construct two edge-disjoint Hamiltonian cycles and two-equal path cover in an n-dimensional augmented cube AQn.