Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2016, 10:1, 78-85
Volume 23, No 1, 2016, P. 51-64
UDC 519.95
I. S. Bykov
On locally balanced Gray codes
Abstract:
We consider locally balanced Gray codes. We say that a Gray code is locally balanced if each “short” subword of transition sequence contains all letters of the set {1, 2, … , n}. The minimal length of such subwords is called the window width of the code. We show that for each n ≥ 3 there exists a Gray code with window width not greater than$n + 3 \lfloor\log n\rfloor$.
Tab. 2, bibliogr. 10.
Keywords: Gray code, Hamilton cycle, n-cube, window width code.
DOI: 10.17377/daio.2016.23.497
Igor S. Bykov 1
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: patrick.no10@gmail.com
Received 9 June 2015
Revised 17 August 2015
References
[1] O. P. Godovykh, A study of uniform Gray codes, Materialy yubileinoi 50-i mezhdunarodnoi nauchnoi studencheskoi konferentsii “Student i nauchno-tekhnicheskii progress”. Proc. 50th Int. Student Sci. Conf. “Students and Progress in Science and Technology”, Novosibirsk, Russia, Apr. 13–19, 2012, p. 133, NGU, Novosibirsk, 2012.[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.
[3] L. A. Korolenko, Finding strongly uniform Gray codes, Materialy 48-i mezhdunarodnoi nauchnoi studencheskoi konferentsii “Student i nauchno-tekhnicheskii progress”. Proc. 48th Int. Student Sci. Conf. “Students and Progress in Science and Technology”, Novosibirsk, Russia, Apr. 10–14, 2010, p. 162, NGU, Novosibirsk, 2010.
[4] F. Aguil´o and A. Miralles, Frobenius’ problem, in Proc. 2005 Eur. Conf. Comb., Graph Theory Appl., Berlin, Germany, Sept. 5–9, 2005, p. 317–322, DMTCS, Nancy, 2005.
[5] Yu. Chebiryak and D. Kroening, Towards a classification of Hamiltonian cycles in the 6-cube, J. Satisf., Boolean Model. Comput., 4, 57–74, 2008.
[6] I. J. Dejter and A. A. Delgado, Classes of Hamilton cycles in the 5-cube, J. Comb. Math. Comb. Comput., 61, 81–95, 2007.
[7] T. Feder and C. Subi, Nearly tight bounds on the number of Hamiltonian circuits of the hypercube and generalizations, Inf. Process. Lett., 109, No. 5, 267–272, 2009.
[8] L. Goddyn and P. Gvozdjak, Binary Gray codes with long bit runs, Electron. J. Comb., 10, No. R27, 1–10, 2003.
[9] H. Haanpää and P. R. J. Östergård, Counting Hamiltonian cycles in bipartite graphs, Math. Comput., 83, No. 286, 979–995, 2014.
[10] C. Savage, A survey of combinatorial Gray codes, SIAM Rev., 39, No. 4, 605–629, 1997.
