Geodesic
On distance Gray codes
Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 2, pp. 5-17.

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

A Gray code of size $n$ is a cyclic sequence of all binary words of length $n$ such that two consecutive words differ exactly in one position. We say that the Gray code is a distance code if the Hamming distance between words located at distance $k$ from each other is equal to $d$. The distance property generalizes the familiar concepts of a locally balanced Gray code. We prove that there are no distance Gray codes with $d=1$ for $k>1$. Some examples of constructing distance Gray codes are given. For one infinite series of parameters, it is proved that there are no distance Gray codes. Tab. 5, bibliogr. 9.
Keywords: $n$-cube, Hamiltonian cycle, Gray code, uniform Gray code
Mots-clés : antipodal Gray code. 
@article{DA_2017_24_2_a0,
     author = {I. S. Bykov and A. L. Perezhogin},
     title = {On distance {Gray} codes},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--17},
     publisher = {mathdoc},
     volume = {24},
     number = {2},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2017_24_2_a0/}
}
TY  - JOUR
AU  - I. S. Bykov
AU  - A. L. Perezhogin
TI  - On distance Gray codes
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2017
SP  - 5
EP  - 17
VL  - 24
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2017_24_2_a0/
LA  - ru
ID  - DA_2017_24_2_a0
ER  - 
%0 Journal Article
%A I. S. Bykov
%A A. L. Perezhogin
%T On distance Gray codes
%J Diskretnyj analiz i issledovanie operacij
%D 2017
%P 5-17
%V 24
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2017_24_2_a0/
%G ru
%F DA_2017_24_2_a0
I. S. Bykov; A. L. Perezhogin. On distance Gray codes. Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 2, pp. 5-17. http://geodesic.mathdoc.fr/item/DA_2017_24_2_a0/

[1] I. S. Bykov, “On locally balanced Gray codes”, J. Appl. Ind. Math., 10:1 (2016), 78–85 | DOI | DOI | MR | Zbl

[2] A. A. Evdokimov, “On enumeration of subsets of a finite set”, Methods of Discrete Analysis for Solving Combinatorial Problems, 34, Izd. Inst. Mat., Novosibirsk, 1980, 8–26 (Russian)

[3] A. L. Perezhogin, “On automorphisms of cycles in an $n$-dimensional Boolean cube”, Diskretn. Anal. Issled. Oper., Ser. 1, 14:3 (2007), 67–79 (Russian) | MR | Zbl

[4] Chang G. J., Eu S.-P., Yeh C.-H., “On the $(n,t)$-antipodal Gray codes”, Theor. Comput. Sci., 374:1–3 (2007), 82–90 | DOI | MR | Zbl

[5] Goddyn L., Gvozdjak P., “Binary Gray codes with long bit runs”, Electron. J. Comb., 10 (2003), R27, 10 pp. | MR | Zbl

[6] Goddyn L., Lawrence G. M., Nemeth E., “Gray codes with optimized run lengths”, Util. Math., 34 (1988), 179–192 | MR | Zbl

[7] Killian C., Savage C., “Antipodal Gray codes”, Discrete Math., 281 (2002), 221–236 | DOI | MR

[8] Knuth D. E., The art of computer programming, Addison-Wesley, Reading, MA, 2004 | MR

[9] Savage C., “A survey of combinatorial Gray codes”, SIAM Rev., 39:4 (1996), 605–629 | DOI | MR