Monotone Gray codes and the middle levels problem

DOI10.1016/0097-3165(95)90091-8zbMATH Open0827.05039OpenAlexW2029196217WikidataQ56084127 ScholiaQ56084127MaRDI QIDQ1805053FDOQ1805053

Peter Winkler, Carla D. Savage

Publication date: 27 November 1995

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0097-3165(95)90091-8

Recommendations

• On the central levels problem
• Gray codes and symmetric chains
• Gray codes and symmetric chains
• Proof of the middle levels conjecture
• Gray codes with restricted density

zbMATH Keywords

Gray codelong cycleshamiltonian pathmiddle-level problem

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Applications of graph theory to circuits and networks (94C15)

Cites Work

• Optimal numberings and isoperimetric problems on graphs
• Title not available (Why is that?)
• Efficient generation of the binary reflected gray code and its applications
• Lexicographic matchings cannot form Hamiltonian cycles
• Explicit matchings in the middle levels of the Boolean lattice
• Long cycles in vertex-transitive graphs
• A technique for generating Gray codes
• Title not available (Why is that?)
• A Technique for Generating Specialized Gray Codes
• The antipodal layers problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (31)

• The \(q\)-analog of the middle levels problem
• Constructive techniques for labeling constant weight Gray codes with applications to minimal generating sets of semigroups
• Bipartite Kneser graphs are Hamiltonian
• Long cycles in the middle two layers of the discrete cube
• Efficient Computation of Middle Levels Gray Codes
• On generalized middle-level problem
• Kneser graphs are Hamiltonian for \(n\geq 3k\)
• Title not available (Why is that?)
• A minimum-change version of the Chung-Feller theorem for Dyck paths
• Gray codes and overlap cycles for restricted weight words
• Antipodal Gray codes
• An update on the middle levels problem
• Permutational labelling of constant weight Gray codes
• On the \((n,t)\)-antipodal Gray codes
• Gray codes with restricted density
• Proof of the middle levels conjecture
• Triangle-free Hamiltonian Kneser graphs
• Bipartite Kneser graphs are Hamiltonian
• On a Combinatorial Generation Problem of Knuth
• Gray codes and symmetric chains
• Hamiltonian cycles and symmetric chains in Boolean lattices.
• The coolest way to generate binary strings
• Trimming and gluing Gray codes
• On the central levels problem
• A constant-time algorithm for middle levels Gray codes
• Minimal enumerations of subsets of a finite set and the middle level problem
• Hamiltonian cycles in Kneser graphs for \(n=2k+2\)
• A construction of Gray codes inducing complete graphs
• Counting techniques to label constant weight Gray codes with links to minimal generating sets of semigroups
• A short proof of the middle levels theorem
• On the snake-in-the-box codes for rank modulation under Kendall's \(\tau \)-metric

This page was built for publication: Monotone Gray codes and the middle levels problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1805053)