Journal article
Proof of Komlós's conjecture on Hamiltonian subsets
- Abstract:
- Komlós conjectured in 1981 that among all graphs with minimum degree at least d, the complete graph K d+1 minimises the number of Hamiltonian subsets, where a subset of vertices is Hamiltonian if it contains a spanning cycle. We prove this conjecture when d is sufficiently large. In fact we prove a stronger result: for large d, any graph G with average degree at least d contains almost twice as many Hamiltonian subsets as K d+1 , unless G is isomorphic to K d+1 or a certain other graph which we specify
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 570.0KB, Terms of use)
-
- Publisher copy:
- 10.1112/plms.12059
Authors
+ European Research Council
More from this funder
- Funding agency for:
- Kim, J
- Sharifzadeh, M
- Staden, K
- Liu, H
- Grant:
- 306349
- 306493
- 306493
- ECF-2016-523
+ Engineering and Physical Sciences Research Council
More from this funder
- Funding agency for:
- Liu, H
- Grant:
- ECF-2016-523
- EP/K012045/1
- Publisher:
- London Mathematical Society
- Journal:
- Proceedings of the London Mathematical Society More from this journal
- Volume:
- 115
- Issue:
- 5
- Pages:
- 974-1013
- Publication date:
- 2017-07-17
- Acceptance date:
- 2017-06-13
- DOI:
- EISSN:
-
1460-244X
- ISSN:
-
0024-6115
- Keywords:
- Pubs id:
-
pubs:820651
- UUID:
-
uuid:ae80e8fe-410e-4a0b-8e3f-f23446e3387f
- Local pid:
-
pubs:820651
- Source identifiers:
-
820651
- Deposit date:
-
2018-01-20
Terms of use
- Copyright holder:
- © 2017 London Mathematical Society
- Copyright date:
- 2017
- Notes:
- This is the author accepted manuscript following peer review version of the article. The final version is available online from London Mathematical Society at: 10.1112/plms.12059
If you are the owner of this record, you can report an update to it here: Report update to this record