Geodesic
Construction of Hamiltonian cycles with a~given range of directions of edges in the Boolean $n$-dimensional cube
Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 2, pp. 75-83.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2012_19_2_a4,
     author = {V. N. Potapov},
     title = {Construction of {Hamiltonian} cycles with a~given range of directions of edges in the {Boolean} $n$-dimensional cube},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {75--83},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2012_19_2_a4/}
}
TY  - JOUR
AU  - V. N. Potapov
TI  - Construction of Hamiltonian cycles with a~given range of directions of edges in the Boolean $n$-dimensional cube
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2012
SP  - 75
EP  - 83
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2012_19_2_a4/
LA  - ru
ID  - DA_2012_19_2_a4
ER  - 
%0 Journal Article
%A V. N. Potapov
%T Construction of Hamiltonian cycles with a~given range of directions of edges in the Boolean $n$-dimensional cube
%J Diskretnyj analiz i issledovanie operacij
%D 2012
%P 75-83
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2012_19_2_a4/
%G ru
%F DA_2012_19_2_a4
V. N. Potapov. Construction of Hamiltonian cycles with a~given range of directions of edges in the Boolean $n$-dimensional cube. Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 2, pp. 75-83. http://geodesic.mathdoc.fr/item/DA_2012_19_2_a4/

[1] Perezhogin A. L., Potapov V. N., “O chisle gamiltonovykh tsiklov v bulevom kube”, Diskret. analiz i issled. operatsii. Ser. 1, 8:2 (2001), 52–62 | MR | Zbl

[2] Perezhogin A. L., Potapov V. N., “O covershennykh parosochetaniyakh v dvoichnom kube”, Diskretnye modeli v teorii upravlyayuschikh sistem, Tr. VII mezhdunar. konf. (Pokrovskoe, 4–6 marta 2006 g.), MAKS Press, M., 2006, 272–277

[3] Perezhogin A. L., “Ob avtomorfizmakh tsiklov v $n$-mernom bulevom kube”, Diskret. analiz i issled. operatsii. Ser. 1, 14:3 (2007), 67–79 | MR | Zbl

[4] Potapov V. N., “O spektrakh gamiltonovykh tsiklov v bulevom $n$-kube”, Mat. XVII mezhdunar. shkoly-seminara “Sintez i slozhnost upravlyayuschikh sistem” im. akademika O. B. Lupanova (Novosibirsk, 27 oktyabrya – 1 noyabrya 2008 g.), In-t matematiki SO RAN, Novosibirsk, 2008, 137–140

[5] Bhat G. S., Savage C. D., “Balanced Gray codes”, Electron. J. Comb., 3 (1996), Research Paper 25 | MR | Zbl

[6] Feder T., Subi C., “Nearly tight bounds on the number of Hamiltonian circuits of the hypercube and generalizations”, Inform. Process. Lett., 109:5 (2009), 267–272 | DOI | MR | Zbl

[7] Fink J., “Perfect matchings extend to Hamilton cycles in hypercubes”, J. Comb. Theory Ser. B, 97:6 (2007), 1074–1076 | DOI | MR | Zbl

[8] Knuth D. E., The art of computer programming, v. 4, Addison–Wesley, New-Jersey, 2009, 944 pp. | MR | Zbl

[9] Kreweras G., “Matchings and Hamiltonian cycles on hypercubes”, Bull. Inst. Comb. Appl., 16 (1996), 87–91 | MR | Zbl

[10] Suparta I. N., “A simple proof for the existence of exponentially balanced Gray codes”, Electron. J. Comb., 12 (2005), Note 19 | MR