Volume 19, No 2, 2012, P. 76-84

UDC 519.95
V. N. Potapov 
Construction of hamiltonian cycles with a given range of directions of edges in the boolean n-dimensional cube

Abstract:
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.

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

Potapov Vladimir Nikolaevich ¹
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: vpotapov@math.nsc.ru