Two Edge-Disjoint Hamiltonian Cycles and Two-Equal Path Partition in Augmented Cubes
Ruo-Wei Hung, Chien-Chih Liao · 2011
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, denoted by 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 they are node-symmetric. Recently, some interesting properties of AQn were investigated. A graph G contains twoequal path partition if for any two distinct pairs of nodes (us, ut) and (vs, vt) of G, there exist two node-disjoint paths P and Q satisfying that (1) P joins us and ut, and Q joins vs and vt, (2) |P | = |Q|, and (3) every node of G appears in one path exactly once. In this paper, we first use a simple recursive method to construct two edge-disjoint Hamiltonian cycles in AQn for any integer n � 3. We then show that the n-dimensional augmented cube AQn, with n � 2, contains twoequal path partition. Index Terms—edge-disjoint Hamiltonian cycles, two-equal path partition, augmented cubes, hypercubes, parallel computing