The prism over the middle-levels graph is Hamiltonian
From MaRDI portal
Publication:2490424
Let \textbf{B}\(_k\) be the bipartite graph whose vertices are subsets of size \(k\) or \(k+1\) of the set \(\{1,2,\dots,2k+1\}\), and whose edges represent the inclusion between two such subsets. The authors prove that the prism over \textbf{B}\(_k\) is Hamiltonian and that \textbf{B}\(_k\) has a closed spanning 2-trail.
Recommendations
- The prism of the acyclic orientation graph is Hamiltonian
- Prism‐hamiltonicity of triangulations
- On hamiltonian cycles in the prism over the odd graphs
- A degree sum condition for graphs to be prism Hamiltonian
- scientific article; zbMATH DE number 4087694
- Hamiltonian decompositions of prisms over cubic graphs
- Hamiltonian decomposition of prisms over cubic graphs
- Hamilton cycles in prisms
- A counterexample to prism-Hamiltonicity of 3-connected planar graphs
- Hamiltonian decompositions of prisms over complete 3-uniform hypergraphs
Cites work
- A characterization of Hamiltonian prisms
- An explicit 1-factorization in the middle of the Boolean lattice
- Explicit matchings in the middle levels of the Boolean lattice
- Hamilton cycles in prisms
- Hamiltonian decompositions of prisms over cubic graphs
- scientific article; zbMATH DE number 3838053 (Why is no real title available?)
- scientific article; zbMATH DE number 68918 (Why is no real title available?)
- scientific article; zbMATH DE number 1156578 (Why is no real title available?)
- scientific article; zbMATH DE number 1439443 (Why is no real title available?)
- Lexicographic matchings cannot form Hamiltonian cycles
Cited in
(16)- A degree sum condition for graphs to be prism Hamiltonian
- An update on the middle levels problem
- Trimming and gluing Gray codes
- A constant-time algorithm for middle levels Gray codes
- Proof of the middle levels conjecture
- Hamiltonian cycles in Kneser graphs for n=2k+2
- A note on the middle levels problem
- On hamiltonian cycles in the prism over the odd graphs
- scientific article; zbMATH DE number 4087694 (Why is no real title available?)
- On a combinatorial generation problem of Knuth
- Prism‐hamiltonicity of triangulations
- Bipartite Kneser graphs are Hamiltonian
- Bipartite Kneser graphs are Hamiltonian
- A minimum-change version of the Chung-Feller theorem for Dyck paths
- On prism-Hamiltonian bipartite graphs
- On generalized middle-level problem
This page was built for publication: The prism over the middle-levels graph is Hamiltonian
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2490424)
