Construction of Hamiltonian cycles with a~given range of directions of edges in the Boolean $n$-dimensional cube

V. N. Potapov

Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 2, pp. 75-83

Résumé

The spectrum of a Hamiltonian cycle (Gray code) in a Boolean $n$-cube is the $n$-tuple $a=(a_1,\dots,a_n)$, where $a_i$ is the number of edges from the $i$-th parallel class in the cycle. There exist well known necessary conditions for existence of the Gray code with the spectrum $a$: the numbers $a_i$ are even and for any $k=1,\dots,n$ the sum of $k$ arbitrary components of $a$ is not less than $2^k$. We prove existence of a number $N$ such that if the necessary conditions on the spectrum are sufficient for existence of a Hamiltonian cycle with such spectrum in the Boolean $N$-dimensional cube, then the above conditions are sufficient for all dimensions. Bibliogr. 10.

Détail

Keywords: Hamiltonian cycle, perfect matching, Boolean cube, Gray code.