Towards a simple construction method for Hamiltonian decomposition of the hypercube
Siang Wun Song · DIMACS series in discrete mathematics and theoretical computer science · 1995
. We consider the problem of Hamiltonian decomposition on the hypercube. It is known that there exist bn=2c edge-disjoint Hamiltonian cycles on a binary n-cube. However, there are still no simple algorithms to construct such cycles. We present some promising results that may lead to a very simple method to obtain the Hamiltonian decomposition. The binary n-cube is equivalent to the Cartesian product of cycles of length four (C4 \\Theta C4 : : : \\Theta C4 ). Case n = 4 is trivial. For the case n = 6, we first partition the set of edges of the C 4 \\Theta C 4 \\Theta C 4 into 12 disjoint cycles of length 16. We then present an operator to merge the cycles to produce the desired Hamiltonian cycles. In general the edge set of n=2 products C 4 \\Theta C 4 : : : \\Theta C 4 , can be partitioned into n2 n =32 disjoint cycles of length 16. It remains to formalize the merge operator in the general case. 1. Introduction The problem of finding edge-disjoint cycles on a hypercube can be important i...