Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Binary gray codes with long bit runs | Binary gray codes with long bit runs Luis Goddyn Pavol Gvozdjak Department of Mathematics Simon Fraser University Burnaby BC Canada goddyn@ gvozdjak@ Submitted Dec 21 2001 Accepted Jun 17 2003 Published Jun 27 2003 MR Subject Classifications 05C38 05C45 68R15 Abstract We show that there exists an n-bit cyclic binary Gray code all of whose bit runs have length at least n 3log2 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 log2 n consecutive words. Such Gray codes are locally distance preserving in that Hamming distance equals index separation for nearby words in the sequence. Keywords cyclic binary Gray code Hamming distance preserving Hamilton cycle Hamilton circuit n-cube gap spread threshold minimum run length. 1 Introduction We use the language of graph theory but where a circuit is a closed walk with no repeated internal vertices. A cycle is an orbit of a permutation acting on a set. The n-cube Qn is the graph whose vertices are the words of length n on the alphabet 0 1 two vertices are adjacent if they differ in exactly one coordinate. The transition of an edge vw in Qn is the index 5vw G 1 2 . n of the coordinate or bit in which v and w differ. An n-bit cyclic binary Gray code is a Hamilton circuit in Qn. Frank Gray 3 described an elementary family of reflected Gray codes RGC which has seen countless applications. Certain applications in engineering statistics and computer science require specialized Gray codes with properties not possessed by the RGC. We refer to Savage 6 for more information on such variations. This paper is concerned with Gray codes for which any two edges which have equal transitions are well separated along the circuit. Research supported by the Natural Sciences and Engineering Research Council of Canada THE ELECTRONIC JOURNAL OF COMBINATORICS 10 2003 R27 1 Formally the minimum .
