zbMATH — the first resource for mathematics

Binary Gray codes with long bit runs. (English) Zbl 1023.05080
Electron. J. Comb. 10, Research paper R27, 10 p. (2003); printed version J. Comb. 10, No. 3 (2003).
Summary: We show that there exists an \(n\)-bit cyclic binary Gray code all of whose bit runs have length at least \(n - 3\log_2 n\). That is, there exists a cyclic ordering of \(\{0,1\}^n\) such that adjacent words differ in exactly one (coordinate) bit, and such that no bit changes its value twice in any subsequence of \(n-3\log_2 n\) consecutive words. Such Gray codes are ‘locally distance preserving’ in that Hamming distance equals index separation for nearby words in the sequence.

05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
68R15 Combinatorics on words
Full Text: EMIS EuDML