Volume 19, No 2, 2012, P. 7684
UDC 519.95
V. N. Potapov
Construction of hamiltonian cycles with a given range of directions of edges in the boolean ndimensional 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}
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
email: vpotapov@math.nsc.ru
