Show simple item record

dc.contributor.author
Mütze, Torsten
dc.contributor.author
Nummenpalo, Jerri
dc.contributor.author
Walczak, Bartosz
dc.date.accessioned
2021-06-16T20:03:06Z
dc.date.available
2020-12-24T03:32:33Z
dc.date.available
2021-01-05T09:06:57Z
dc.date.available
2021-06-16T20:03:06Z
dc.date.issued
2021-06
dc.identifier.issn
0024-6107
dc.identifier.issn
1469-7750
dc.identifier.other
10.1112/jlms.12406
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/458477
dc.identifier.doi
10.3929/ethz-b-000458477
dc.description.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, horizontal ellipsis ,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.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Wiley
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
dc.subject
05C45
en_US
dc.subject
94B25 (primary)
en_US
dc.title
Sparse Kneser graphs are Hamiltonian
en_US
dc.type
Journal Article
dc.rights.license
Creative Commons Attribution 4.0 International
dc.date.published
2020-12-10
ethz.journal.title
Journal of the London Mathematical Society
ethz.journal.volume
103
en_US
ethz.journal.issue
4
en_US
ethz.journal.abbreviated
J. London Math. Soc.
ethz.pages.start
1253
en_US
ethz.pages.end
1275
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.identifier.wos
ethz.identifier.scopus
ethz.publication.place
Oxford
en_US
ethz.publication.status
published
en_US
ethz.date.deposited
2020-12-24T03:32:37Z
ethz.source
WOS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2021-06-16T20:03:19Z
ethz.rosetta.lastUpdated
2022-03-29T08:49:27Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Sparse%20Kneser%20graphs%20are%20Hamiltonian&rft.jtitle=Journal%20of%20the%20London%20Mathematical%20Society&rft.date=2021-06&rft.volume=103&rft.issue=4&rft.spage=1253&rft.epage=1275&rft.issn=0024-6107&1469-7750&rft.au=M%C3%BCtze,%20Torsten&Nummenpalo,%20Jerri&Walczak,%20Bartosz&rft.genre=article&rft_id=info:doi/10.1112/jlms.12406&
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record