Sparse Kneser graphs are Hamiltonian

DOI10.1145/3188745.3188834zbMATH Open1428.05179arXiv1711.01636OpenAlexW2767495301MaRDI QIDQ5230348FDOQ5230348

Authors: Torsten Mütze, Jerri Nummenpalo, Bartosz Walczak 

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Abstract: For integers $kgeq1$ and $ngeq2k+1$, the Kneser graph $K(n,k)$ is the graph whose vertices are the $k$-element subsets of $1,ldots,n$ and whose edges connect pairs of subsets that are disjoint. The Kneser graphs of the form $K(2k+1,k)$ are also known as the odd graphs. We settle an old problem due to Meredith, Lloyd, and Biggs from the 1970s, proving that for every $kgeq3$, the odd graph $K(2k+1,k)$ has a Hamilton cycle. This and a known conditional result due to Johnson imply that all Kneser graphs of the form $K(2k+2^a,k)$ with $kgeq3$ and $ageq0$ have a Hamilton cycle. We also prove that $K(2k+1,k)$ has at least $2^{2^{k-6}}$ distinct Hamilton cycles for $kgeq6$. Our proofs are based on a reduction of the Hamiltonicity problem in the odd graph to the problem of finding a spanning tree in a suitably defined hypergraph on Dyck words.

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

Recommendations

• Sparse Kneser graphs are Hamiltonian
• Kneser graphs are Hamiltonian for \(n\geq 3k\)
• Triangle-free Hamiltonian Kneser graphs
• Bipartite Kneser graphs are Hamiltonian
• Hamiltonian Kneser graphs

zbMATH Keywords

Kneser graphHamilton cyclevertex-transitive graphodd graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Cited In (11)

• On a combinatorial generation problem of Knuth
• Spectrum of Johnson graphs
• Kneser graphs are Hamiltonian for \(n\geq 3k\)
• Sparse Kneser graphs are Hamiltonian
• Short proof that Kneser graphs are Hamiltonian for \(n \geqslant 4k\)
• The toughness of Kneser graphs
• A numeral system for the middle-levels graphs
• Bipartite Kneser graphs are Hamiltonian
• Title not available (Why is that?)
• On semi-transitive orientability of Kneser graphs and their complements
• Hamiltonian cycles in Kneser graphs for \(n=2k+2\)

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

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