Journal title
Electronic Notes in Discrete Mathematics
DOI
10.1016/j.endm.2017.07.029
Volume
61
Last updated
2021-10-19T13:22:31.017+01:00
Page
727-733
Abstract
© 2017 Elsevier B.V. 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.
Symplectic ID
820836
Submitted to ORA
Off
Publication type
Journal Article
Publication date
1 August 2017