Cyclic enumeration of binary words of length n, where each pair of adjacent words differs in exactly one index, is called n-dimensional Gray code. Gray code determines hamiltonian cycle in boolean n-cube. In this paper we give a review of constructions and classifications of Gray codes. Constructions are divided into three main groups: recursive, toric and stream. We also give some of Gray code properties, as an example of applications of these constructions. In particular, we consider spectrum of edge directions, graphs of 2-subwords in transition sequence, local uniformity and others. Also some unresolved problems are given.

Gray code, hamiltonian cycle, boolean cube, transition sequence

Mathematical problems and theory of numerical methods

Perezhogin Aleksey Lvovich,  ,  orcid.org/0000-0001-7260-2340,  Sobolev Institute of Mathematics

Bykov Igor Sergeevich,  ,  orcid.org/0000-0001-8475-9847,  Novosibirsk State University