Gray codes with restricted density
type: Item
instance of: scholarly article
title: Gray codes with restricted density
zbMATH Open document ID: 0572.05042
DOI: 10.1016/0012-365X(84)90179-1
author: Doug Wiedemann
author: Marshall W. Buck
published in: Discrete Mathematics
publication date: 1984-01-01T00:00:00Z
review text: Define two k-sets of a totally ordered n-set to be adjacent whenever their symmetric difference is an interval of length 2. This paper shows the resulting bipartite graph has a Hamiltonian path whenever the size of the two parts differ by at most 1. Simple necessary and sufficient conditions on n and k are given. Furthermore, a low degree product of this graph with the complete graph K(2) is shown to have a Hamiltonian circuit whenever the graph is non-trivial. The authors have written computer programs for producing Hamiltonian paths and circuits for these graphs, but the paper does not mention this. The example after proposition 1 contains a typographical error in that the vectors 001110 and 011100 are interchanged. The paper also considers some related problems and gives some examples and proofs in support of a general conjecture. The following is included as a special case. Conjecture: it is possible to order the binary \((2k+1)\)-tuples with k or \(k+1\) ones such that consecutive tuples differ in precisely one component (with the first tuple considered consecutive to the last). This is related to the Hamiltonicity problem of the odd graphs. A concurrent paper by \textit{P. Eades}, \textit{T. Hickey} and \textit{R. Read} [J. Assoc. Comput. Machin. 31, 19-29 (1984)] gives a different proof of the Hamiltonian path result. The complexity of the two proofs is roughly the same.
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 94B99
zbMATH DE Number: 3912423
zbMATH Keywords: Hamiltonian path
zbMATH Keywords: Gray code
zbMATH Keywords: Hamiltonian circuit
MaRDI profile type: Publication
cites work: Hamiltonian cycles in the cartesian product of a tree and a cycle
cites work: Transposition Graphs
cites work: Gray codes in graphs of subsets
cites work: Some Simple Applications of the Travelling Salesman Problem
cites work: Q3936208
description: scientific article; zbMATH DE number 3912423