Monotone Gray codes and the middle levels problem

DOI10.1016/0097-3165(95)90091-8MaRDI QIDQ1805053zbMATH OpenOpenAlexWikidataFDO

Authors Carla D. Savage, Peter Winkler

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

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)

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

Cites work

• scientific article; zbMATH DE number 3916312 (Why is no real title available?)
• scientific article; zbMATH DE number 4070937 (Why is no real title available?)
• scientific article; zbMATH DE number 4087600 (Why is no real title available?)
• scientific article; zbMATH DE number 17941 (Why is no real title available?)
• scientific article; zbMATH DE number 140139 (Why is no real title available?)
• scientific article; zbMATH DE number 866658 (Why is no real title available?)
• A Technique for Generating Specialized Gray Codes
• A technique for generating Gray codes
• Efficient generation of the binary reflected gray code and its applications
• Explicit matchings in the middle levels of the Boolean lattice
• Lexicographic matchings cannot form Hamiltonian cycles
• Long cycles in vertex-transitive graphs
• Optimal numberings and isoperimetric problems on graphs
• The antipodal layers problem

Cited in

(35)

• The q-analog of the middle levels problem
• Constructive techniques for labeling constant weight Gray codes with applications to minimal generating sets of semigroups
• Long cycles in the middle two layers of the discrete cube
• Bipartite Kneser graphs are Hamiltonian
• On a combinatorial generation problem of Knuth
• Efficient Computation of Middle Levels Gray Codes
• On generalized middle-level problem
• Kneser graphs are Hamiltonian for \(n\geq 3k\)
• A minimum-change version of the Chung-Feller theorem for Dyck paths
• Gray codes and overlap cycles for restricted weight words
• An update on the middle levels problem
• Antipodal Gray codes
• On the \((n,t)\)-antipodal Gray codes
• Permutational labelling of constant weight Gray codes
• Gray codes with restricted density
• Proof of the middle levels conjecture
• Triangle-free Hamiltonian Kneser graphs
• On Hamilton cycles in highly symmetric graphs
• Bipartite Kneser graphs are Hamiltonian
• The first three levels of an order preserving Hamiltonian path in the subset lattice
• Gray codes and symmetric chains
• Gray codes and symmetric chains
• Hamiltonian cycles and symmetric chains in Boolean lattices.
• The coolest way to generate binary strings
• Efficient computation of middle levels Gray codes
• Trimming and gluing Gray codes
• Trimming and gluing Gray codes
• On the central levels problem
• A constant-time algorithm for middle levels Gray codes
• Hamiltonian cycles in Kneser graphs for \(n=2k+2\)
• A construction of Gray codes inducing complete graphs
• Minimal enumerations of subsets of a finite set and the middle level problem
• 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)