Bipartite Kneser graphs are Hamiltonian

DOI10.1007/S00493-016-3434-6MaRDI QIDQ5895045zbMATH OpenOpenAlexFDO

Authors Torsten Mütze, Pascal Su

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

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

Abstract: For integers $kgeq1$ and $ngeq2k+1$ the Kneser graph $K(n,k)$ has as vertices all $k$-element subsets of $[n]:=1,2,ldots,n$ and an edge between any two vertices (=sets) that are disjoint. The bipartite Kneser graph $H(n,k)$ has as vertices all $k$-element and $(n-k)$-element subsets of $[n]$ and an edge between any two vertices where one is a subset of the other. It has long been conjectured that all Kneser graphs and bipartite Kneser graphs except the Petersen graph $K(5,2)$ have a Hamilton cycle. The main contribution of this paper is proving this conjecture for bipartite Kneser graphs $H(n,k)$. We also establish the existence of cycles that visit almost all vertices in Kneser graphs $K(n,k)$ when $n=2k+o(k)$, generalizing and improving upon previous results on this problem.

Recommendations

• Bipartite Kneser graphs are Hamiltonian
• scientific article; zbMATH DE number 140139
• Hamiltonian Kneser graphs
• On Hamiltonian bipartite graphs
• scientific article; zbMATH DE number 1289752
• Two Hamilton cycles in bipartite reflective Kneser graphs
• Bipartite graphs with every \(k\)-matching in a Hamiltonian cycle.
• scientific article; zbMATH DE number 11998
• Hamiltonian cycles in bipartite graphs
• Hamiltonicity of bipartite biclaw-free graphs

Cites work

• scientific article; zbMATH DE number 140139 (Why is no real title available?)
• scientific article; zbMATH DE number 3600077 (Why is no real title available?)
• scientific article; zbMATH DE number 2059939 (Why is no real title available?)
• scientific article; zbMATH DE number 866658 (Why is no real title available?)
• A Survey of Combinatorial Gray Codes
• A survey of the theory of hypercube graphs
• An explicit 1-factorization in the middle of the Boolean lattice
• An inductive construction for Hamilton cycles in Kneser graphs
• An update on the middle levels problem
• Colorings of diagrams of interval orders and \(\alpha\)-sequences of sets
• Explicit matchings in the middle levels of the Boolean lattice
• Gray codes with restricted density
• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Hamiltonian Kneser graphs
• Hamiltonian uniform subset graphs
• Kneser graphs are Hamiltonian for \(n\geq 3k\)
• Kneser's conjecture, chromatic number, and homotopy
• Lexicographic matchings cannot form Hamiltonian cycles
• Long cycles in the middle two layers of the discrete cube
• Monotone Gray codes and the middle levels problem
• On generalized middle-level problem
• The Rugby footballers of Croam
• The antipodal layers problem
• The prism over the middle-levels graph is Hamiltonian
• Triangle-free Hamiltonian Kneser graphs
• Updating the hamiltonian problem—A survey

Cited in

(19)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5895045)