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

摘要

In this paper, we construct two edge-disjoint Hamiltonian cycles (paths) of a n-dimensional augmented cube AQn, for any integer n > 3. In addition, we prove that AQn, with n > 2, contains two-equal path partition. In the construction of two edge-disjoint Hamiltonian cycles (paths) of AQn, some edges are not used. It is interesting to see if there are more edge-disjoint Hamiltonian cycles of AQn for n > 4. We would like to post it as an open problem to interested readers.