The prism over the middle-levels graph is Hamiltonian

DOI10.1007/S11083-005-9008-7zbMath1089.05041OpenAlexW2016863833MaRDI QIDQ2490424

Zdeněk Ryjáček, Tomáš Kaiser, Moshe Rosenfeld, Peter Horák

Publication date: 2 May 2006

Published in: Order (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11083-005-9008-7

zbMATH Keywords

Hamiltonian graphPrismBipartite graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Related Items (14)

A note on the middle levels problem ⋮ On a Combinatorial Generation Problem of Knuth ⋮ Trimming and gluing Gray codes ⋮ Bipartite Kneser graphs are Hamiltonian ⋮ Unnamed Item ⋮ Bipartite Kneser graphs are Hamiltonian ⋮ On generalized middle-level problem ⋮ A minimum-change version of the Chung-Feller theorem for Dyck paths ⋮ Proof of the middle levels conjecture ⋮ A constant-time algorithm for middle levels Gray codes ⋮ On hamiltonian cycles in the prism over the odd graphs ⋮ Hamiltonian Cycles in Kneser Graphs for ⋮ A degree sum condition for graphs to be prism Hamiltonian ⋮ An update on the middle levels problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lexicographic matchings cannot form Hamiltonian cycles
• Explicit matchings in the middle levels of the Boolean lattice
• An explicit 1-factorization in the middle of the Boolean lattice
• Hamiltonian decompositions of prisms over cubic graphs
• A characterization of Hamiltonian prisms
• Hamilton cycles in prisms

This page was built for publication: The prism over the middle-levels graph is Hamiltonian