Lexicographic matchings cannot form Hamiltonian cycles

DOI10.1007/BF00337620zbMath0657.05055OpenAlexW1968184858MaRDI QIDQ1110538

Bill Sands, Dwight Duffus, Robert E. Woodrow

Publication date: 1988

Published in: Order (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00337620

zbMATH Keywords

bipartite graphHamiltonian cyclelexicographic matchings

Mathematics Subject Classification ID

Partial orders, general (06A06) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Eulerian and Hamiltonian graphs (05C45)

Related Items (16)

Some Results on Fractional Graph Theory ⋮ On a Combinatorial Generation Problem of Knuth ⋮ Explicit matchings in the middle levels of the Boolean lattice ⋮ Trimming and gluing Gray codes ⋮ Construction of 2-factors in the middle layer of the discrete cube ⋮ Bipartite Kneser graphs are Hamiltonian ⋮ Bipartite Kneser graphs are Hamiltonian ⋮ The prism over the middle-levels graph is Hamiltonian ⋮ Minimal enumerations of subsets of a finite set and the middle level problem ⋮ A minimum-change version of the Chung-Feller theorem for Dyck paths ⋮ Proof of the middle levels conjecture ⋮ Monotone Gray codes and the middle levels problem ⋮ A constant-time algorithm for middle levels Gray codes ⋮ Boolean layer cakes ⋮ An update on the middle levels problem ⋮ The antipodal layers problem

Cites Work

• Two Hamilton cycles in bipartite reflective Kneser graphs
• Explicit matchings in the middle levels of the Boolean lattice
• Lexicographic matching in Boolean algebras

This page was built for publication: Lexicographic matchings cannot form Hamiltonian cycles