Volume 24, No 2, 2017, P. 5-17

UDC 519.17
I. S. Bykov and A. L. Perezhogin
On distance Gray codes

Abstract:
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, antipodal Gray code.

DOI: 10.17377/daio.2017.24.545

Igor S. Bykov ²
Alexey L. Perezhogin ^1,2
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: patrick.no10@gmail.com, pereal@math.nsc.ru

Received 19 May 2016
Revised 16 September 2016

References

[1] I. S. Bykov, On locally balanced Gray codes, Diskretn. Anal. Issled. Oper., 23, No. 1, 51–64, 2016 [Russian]. Translated in J. Appl. Ind. Math., 10, No. 1, 78–85, 2016.

[2] A. A. Evdokimov, On enumeration of subsets of a finite set, in Metody diskretnogo analiza v reshenii kombinatornykh zadach (Methods of Discrete Analysis for Solving Combinatorial Problems), Vol. 34, pp. 8–26, Izd. Inst. Mat., Novosibirsk, 1980 [Russian].

[3] A. L. Perezhogin, On automorphisms of cycles in an $n$-dimensional Boolean cube, Diskretn. Anal. Issled. Oper., Ser. 1, 14, No. 3, 67–79, 2007 [Russian].

[4] G. J. Chang, S.-P. Eu, and C.-H. Yeh, On the ($n, t$)-antipodal Gray codes, Theor. Comput. Sci., 374, No. 1–3, 82–90, 2007.

[5] L. Goddyn and P. Gvozdjak, Binary Gray codes with long bit runs, Electron. J. Comb., 10, No. R27, 1–10, 2003.

[6] L. Goddyn, G. M. Lawrence, and E. Nemeth, Gray codes with opti?mized run lengths, Util. Math., 34, 179–192, 1988.

[7] C. Killian and C. Savage, Antipodal Gray codes, Discrete Math, 281, 221–236, 2002.

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

[9] C. Savage, A survey of combinatorial Gray codes, SIAM Rev., 39, No. 4, 605–629, 1997.