Bipartite Kneser graphs are Hamiltonian

Abstract

For integers $k\ge 1$ and $n\ge 2k+1$ the Kneser graph $K(n,k)$ has as vertices all $k$-element subsets of $[n]:=\{1,2,\dots ,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.

Cited by in corpus (9)

• Matching number, Hamiltonian graphs and discrete magnetic Laplacians
• Trimming and gluing Gray codes
• Sparse Kneser graphs are Hamiltonian
• Some algebraic properties of bipartite Kneser graphs
• Johnson graphs are panconnected
• The spectrum and automorphism group of the set-inclusion graph
• The super-connectivity of Johnson graphs
• Graphs whose Kronecker covers are bipartite Kneser graphs
• The Toughness of Kneser Graphs