The Library
Sparse Kneser graphs are Hamiltonian
Tools
Mutze, Torsten, Nummenpalo, Jerri and Walczak, Bartosz (2021) Sparse Kneser graphs are Hamiltonian. Journal of the London Mathematical Society, 103 (4). pp. 1253-1275. doi:10.1112/jlms.12406 ISSN 0024-6107.
|
PDF
WRAP-sparse-kneser-graphs-hamiltonian-Mutze-2020.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (952Kb) | Preview |
|
PDF
WRAP-Sparse-Kneser-graphs-Hamiltonian-Mutze-2020.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (1464Kb) |
Official URL: https://doi.org/10.1112/jlms.12406
Abstract
For integers~$k\geq 1$ and~$n\geq 2k+1$, the \emph{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 \emph{odd graphs}.
We settle an old problem due to Meredith, Lloyd, and Biggs from the 1970s, proving that for every~$k\geq 3$, 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~$k\geq 3$ and~$a\geq 0$ have a Hamilton cycle.
We also prove that~$K(2k+1,k)$ has at least~$2^{2^{k-6}}$ distinct Hamilton cycles for~$k\geq 6$.
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.
Item Type: | Journal Article | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||
Journal or Publication Title: | Journal of the London Mathematical Society | ||||||||||||
Publisher: | London Mathematical Society ; Wiley | ||||||||||||
ISSN: | 0024-6107 | ||||||||||||
Official Date: | June 2021 | ||||||||||||
Dates: |
|
||||||||||||
Volume: | 103 | ||||||||||||
Number: | 4 | ||||||||||||
Page Range: | pp. 1253-1275 | ||||||||||||
DOI: | 10.1112/jlms.12406 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||
Date of first compliant deposit: | 7 October 2020 | ||||||||||||
Date of first compliant Open Access: | 14 January 2021 | ||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||
Related URLs: | |||||||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year