Bipartite Kneser graphs are Hamiltonian

DOI10.1007/s00493-016-3434-6zbMath1399.05135arXiv1503.09175OpenAlexW1945596496MaRDI QIDQ5895045

Pascal Su, Torsten Mütze

Publication date: 23 July 2018

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1503.09175

zbMATH Keywords

hypercubeHamiltonian cycleKneser graphbipartite Kneser graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Related Items

Matching number, Hamiltonian graphs and magnetic Laplacian matrices ⋮ Graphs whose Kronecker covers are bipartite Kneser graphs ⋮ The automorphism group of the bipartite Kneser graph ⋮ Some conditions implying stability of graphs ⋮ On the central levels problem ⋮ A short proof of the middle levels theorem ⋮ Cayley properties of the line graphs induced by consecutive layers of the hypercube ⋮ Johnson graphs are panconnected ⋮ The toughness of Kneser graphs ⋮ The general position problem on Kneser graphs and on some graph operations ⋮ On 1-factorizations of bipartite Kneser graphs ⋮ A constant-time algorithm for middle levels Gray codes ⋮ Sparse Kneser graphs are Hamiltonian ⋮ Certain homological invariants of bipartite kneser graphs ⋮ REGULARITY OF POWERS OF BIPARTITE GRAPHS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Long cycles in the middle two layers of the discrete cube
• An inductive construction for Hamilton cycles in Kneser graphs
• Kneser's conjecture, chromatic number, and homotopy
• On generalized middle-level problem
• An update on the middle levels problem
• Gray codes with restricted density
• Hamiltonian uniform subset graphs
• A survey of the theory of hypercube graphs
• 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
• The antipodal layers problem
• Triangle-free Hamiltonian Kneser graphs
• Hamiltonian Kneser graphs
• Monotone Gray codes and the middle levels problem
• The Rugby footballers of Croam
• Kneser graphs are Hamiltonian for \(n\geq 3k\)
• Colorings of diagrams of interval orders and \(\alpha\)-sequences of sets
• The prism over the middle-levels graph is Hamiltonian
• Updating the hamiltonian problem—A survey
• A Survey of Combinatorial Gray Codes
• Hamilton cycles in graphs and hypergraphs: an extremal perspective

This page was built for publication: Bipartite Kneser graphs are Hamiltonian