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.

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