Novosibirsk State University Journal of Information Technologies
Scientic Journal

ISSN 2410-0420 (Online), ISSN 1818-7900 (Print)

Switch to
Russian

All Issues >> Contents: Volume 15, Issue No 4 (2017)

Constructive Approach to Enumerating the Spectra of Gray Codes in Boolean Cubes of Small Dimension
Alexander Evgenievich Malykh, Aleksey Lyvovich Perezhogin

Novosibirsk State University
Ltd. UNIPRO
Institute of Mathematics SB RAS

DOI: DOI 10.25205/1818-7900-2017-15-4-32-42
UDC code: 519.174.2

Abstract
The spectrum of the n-bit Gray code is a set of the number of changes in the corresponding position in the transition to the next codeword. Spectra sets of Gray codes generated by various known constructions are investigated. All the spectra of 7- and 8-bit Gray codes are enumerated.

Key Words
Gray code, Hamiltonian cycle, Boolean cube

How to cite:
Malykh A. E., Perezhogin A. L. Constructive Approach to Enumerating the Spectra of Gray Codes in Boolean Cubes of Small Dimension // Vestnik NSU Series: Information Technologies. - 2017. - Volume 15, Issue No 4. - P. 32-42. - DOI 10.25205/1818-7900-2017-15-4-32-42. - ISSN 1818-7900. (in Russian).

Full Text in Russian

Available in PDF

References
1. Gilbert E. N. Gray codes and paths on the n-cube. Bell System Tech. J., 1958, vol. 37, no. 3, p. 815–826.
2. Savage C. D. A survey of combinatorial Gray codes. SIAM Rev., 1996, vol. 39, no. 4, p. 605–629.
3. Adam A. Truth functions and the problem of their realization by two-terminal graphs. Budapest, Academiai Kiado, 1968.
4. Bhat G. S., Savage C. D. Balanced Gray codes. Electron. J. Comb., 1996, vol. 3, research paper 25.
5. Suparta I. N. A simple proof for the existence of exponentially balanced Gray codes. Electron. J. Comb., 2005, vol. 12, note 19.
6. Evdokimov A. A. On enumeration of subsets of a finite set. Methods of Discrete Analysis for Solving Combinatorial Problems, 34, Novosibirsk, Izd. Inst. Mat., 1980, p. 8–26 (In Russ.).
7. Goddyn L., Lawrence G. M., Nemeth E. Gray codes with optimized run lengths. Util. Math., 1988, vol. 34, p. 179–192.
8. Goddyn L., Gvozdjak P. Binary Gray codes with long bit runs. Electron. J. Comb., 2003, vol. 10, R27.
9. Bykov I. S. On locally balanced Gray codes. J. Appl. Ind. Math., 2016, vol. 10, issue 1, p. 78–85.
10. Bykov S., Perezhogin A. L. On distance Gray codes. J. Appl. Ind. Math., 2016, vol. 11, issue 2, p. 185–192.
11. Knuth D. E. The art of computer programming, vol. 4. Addison, Wesley, New-Jersey, 2009, 944 pp.
12. Parkhomenko P. P. Classification of the Hamiltonian Cycles in Binary Hypercubes. Automation and Remote Control, 2001, vol. 62, no. 6, p. 978–991.
13. Dejter I. J., Delgado A. A. Classes of Hamilton cycles in the 5-cube. J. Comb. Math. Comb. Comput., 2007, vol. 61, p. 81–95.
14. Chebiryak Yu., Kroening D. Towards a classification of Hamiltonian cycles in the 6-cube. J. Satisf., Boolean Model. Comput., 2008, vol. 4, no. 1, p. 57–74.
15. Potapov V. N. Construction of Hamiltonian cycles with a given spectrum of edge directions in an n-dimensional Boolean cube. J. Appl. Ind. Math., 2012, vol. 6, issue 3, p. 339–345.
16. Ramras M. A new method of generating Hamiltonian cycles on the n-cube. Discrete Math., 1990, vol. 85, issue 3, p. 329–331.
17. Dixon E., Goodman S. On the number of Hamiltonian circuits in the n-cube. Proc. Amer. Math. Soc., 1975, vol. 50, p. 500–504.
18. Douglas R. G. Bounds on the number of Hamiltonian circuits in the n-cube. Discrete Math., 1977, vol. 17, no. 2, p. 143–146.
19. Mollard M. Un nouvel encadrement du nombre de cycles hamiltoniens du n-cube. European J. Combinatorics, 1988, vol. 9, no. 1, p. 49–52.

Publication information
Main title Vestnik NSU Series: Information Technologies, Volume 15, Issue No 4 (2017).
Parallel title: Novosibirsk State University Journal of Information Technologies Volume 15, Issue No 4 (2017).

Key title: Vestnik Novosibirskogo gosudarstvennogo universiteta. Seriâ: Informacionnye tehnologii
Abbreviated key title: Vestn. Novosib. Gos. Univ., Ser.: Inf. Tehnol.
Variant title: Vestnik NGU. Seriâ: Informacionnye tehnologii

Year of Publication: 2017
ISSN: 1818-7900 (Print), ISSN 2410-0420 (Online)
Publisher: Novosibirsk State University Press
DSpace handle


|Home Page| |All Issues| |Information for Authors| |Journal Boards| |Ethical principles| |Editorial Policy| |Contact Information| |Publication fee| |Open Access Policy| |Old Site in Russian|

inftech@vestnik.nsu.ru
© 2006-2018, Novosibirsk State University.