Volume 24, No 2, 2017, P. 517
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^{ 2}
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
email: 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, AddisonWesley, Reading, MA, 2004.
[9] C. Savage, A survey of combinatorial Gray codes, SIAM Rev., 39, No. 4, 605–629, 1997.
