Monotone Gray codes and the middle levels problem
type: Item
instance of: scholarly article
title: Monotone Gray codes and the middle levels problem
zbMATH Open document ID: 0827.05039
DOI: 10.1016/0097-3165(95)90091-8
author: Carla D. Savage
author: Peter Winkler
published in: Journal of Combinatorial Theory. Series A
publication date: 1995-11-27T00:00:00Z
review text: An \(n\)-bit Gray code is a hamiltonian path in the \(n\)-hypercube \(\mathbb{Z}_2^n\). Define the weight of a vertex as the number of 1's occurring as its coordinates. An \(n\)-bit Gray code is called monotone if all edges between vertices of weight \(i\) and \(i+1\) precede those between vertices of weight \(j\) and \(j+1\), for all \(i<j\). The main result of this paper is the construction of a monotone \(n\)-bit Gray code for all positive integers \(n\). The proof uses induction on \(n\), but is quite explicit. Let \(G_n (i)\) denote the subgraph of the \(n\)-hypercube induced by vertices of weight \(i\) or \(i+1\); it is not known in general whether \(G_n (i)\) has a hamiltonian path. For \(n=2i+1\) this is known as the middle-level problem. This is a special case of the Lovász conjecture, stating that each vertex-transitive graph has a hamiltonian path. Monotone Gray codes give rise to some long cycles in \(G_n (i)\). Two further problems on hamiltonian paths are proposed here.
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 94C15
zbMATH DE Number: 753616
zbMATH Keywords: Gray code
zbMATH Keywords: hamiltonian path
zbMATH Keywords: middle-level problem
zbMATH Keywords: long cycles
reviewed by: Raffaele Scapellato
MaRDI profile type: Publication
full work available at URL: 0097-3165(95)90091-8
OpenAlex ID: W2029196217
Wikidata QID: Q56084127
cites work: Long cycles in vertex-transitive graphs
cites work: Efficient generation of the binary reflected gray code and its applications
cites work: Q3691702
cites work: Q3803146
cites work: Lexicographic matchings cannot form Hamiltonian cycles
cites work: Q3816026
cites work: Optimal numberings and isoperimetric problems on graphs
cites work: The antipodal layers problem
cites work: Explicit matchings in the middle levels of the Boolean lattice
cites work: A technique for generating Gray codes
cites work: Q4873677
cites work: Q4028522
cites work: Q3975295
cites work: A Technique for Generating Specialized Gray Codes
description: scientific article; zbMATH DE number 753616