The Library
Proof of Komlós's conjecture on Hamiltonian subsets
Tools
Tools
Tools
Kim, Jaehoon, Liu, Hong, Sharifzadeh, Maryam and Staden, Katherine (2017) Proof of Komlós's conjecture on Hamiltonian subsets. Proceedings of the London Mathematical Society, 115 (5). pp. 974-1013. doi:10.1112/plms.12059 ISSN 0024-6115.
|
PDF
WRAP-proof-Komloss-conjecture-subsets-Kim-2017.pdf - Accepted Version - Requires a PDF viewer. Download (1128Kb) | Preview |
Official URL: http://doi.org/10.1112/plms.12059
Abstract
Komlós conjectured in 1981 that among all graphs with minimum degree at least d, the complete graph Kd+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 Kd+1, unless G is isomorphic to Kd+1 or a certain other graph which we specify.
| Item Type: | Journal Article | ||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||||||||||||
| SWORD Depositor: | Library Publications Router | ||||||||||||||||||
| Library of Congress Subject Headings (LCSH): | Hamiltonian graph theory, Hamiltonian systems, Probabilities, Discrete mathematics | ||||||||||||||||||
| Journal or Publication Title: | Proceedings of the London Mathematical Society | ||||||||||||||||||
| Publisher: | Wiley | ||||||||||||||||||
| ISSN: | 0024-6115 | ||||||||||||||||||
| Official Date: | November 2017 | ||||||||||||||||||
| Dates: |
|
||||||||||||||||||
| Volume: | 115 | ||||||||||||||||||
| Number: | 5 | ||||||||||||||||||
| Page Range: | pp. 974-1013 | ||||||||||||||||||
| DOI: | 10.1112/plms.12059 | ||||||||||||||||||
| Status: | Peer Reviewed | ||||||||||||||||||
| Publication Status: | Published | ||||||||||||||||||
| Reuse Statement (publisher, data, author rights): | "This is the peer reviewed version of the following article: Kim, J. , Liu, H. , Sharifzadeh, M. and Staden, K. (2017), Proof of Komlós's conjecture on Hamiltonian subsets. Proc. London Math. Soc., 115: 974-1013. doi:10.1112/plms.12059, which has been published in final form at http://doi.org/10.1112/plms.12059 This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions." | ||||||||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||||||||||||
| Date of first compliant deposit: | 19 November 2019 | ||||||||||||||||||
| Date of first compliant Open Access: | 19 November 2019 | ||||||||||||||||||
| RIOXX Funder/Project Grant: |
|
||||||||||||||||||
| 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
