Gray codes with restricted density (Q1062075): Difference between revisions

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.