The Library
Sparse Kneser graphs are Hamiltonian
Tools
Mutze, Torsten, Nummenpalo, Jerri and Walczak, Bartosz (2018) Sparse Kneser graphs are Hamiltonian. In: 50th Annual ACM Symposium on the Theory of Computing (STOC), Los Angeles, 25-29 Jun 2018. Published in: Proceedings of the 50th Annual ACM Symposium on the Theory of Computing (STOC) pp. 912-919. ISBN 9781450355599. doi:10.1145/3188745.3188834
|
PDF
WRAP-sparse-Kneser-graphs-Hamiltonian-Mutze-2018.pdf - Accepted Version - Requires a PDF viewer. Download (1071Kb) | Preview |
Official URL: https://doi.org/10.1145/3188745.3188834
Abstract
For integers k≥1 and n≥2k+1, the Kneser graph K(n,k) is the graph whose vertices are the k-element subsets of {1,…,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 k≥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+2a,k) with k≥3 and a≥0 have a Hamilton cycle. We also prove that K(2k+1,k) has at least 22k−6 distinct Hamilton cycles for k≥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: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
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 | ||||||
Library of Congress Subject Headings (LCSH): | Hamiltonian graph theory, Graph theory | ||||||
Series Name: | STOC: ACM Symposium on Theory of Computing | ||||||
Journal or Publication Title: | Proceedings of the 50th Annual ACM Symposium on the Theory of Computing (STOC) | ||||||
Publisher: | ACM | ||||||
ISBN: | 9781450355599 | ||||||
Official Date: | June 2018 | ||||||
Dates: |
|
||||||
Page Range: | pp. 912-919 | ||||||
DOI: | 10.1145/3188745.3188834 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Re-use Statement: | In connection with any use by the Owner of the Submitted Version (if accepted) or the Accepted Version or a Minor Revision, Owner shall use best efforts to display the ACM citation, along with a statement substantially similar to the following: © Author | ACM 2018. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in Proceedings of the 50th Annual ACM Symposium on the Theory of Computing (STOC) http://dx.doi.org/10.1145/3188745.3188834 | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 19 June 2019 | ||||||
Date of first compliant Open Access: | 25 June 2019 | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | 50th Annual ACM Symposium on the Theory of Computing (STOC) | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Los Angeles | ||||||
Date(s) of Event: | 25-29 Jun 2018 | ||||||
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