Proof of Komlós's conjecture on Hamiltonian subsets
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...
| Những tác giả chính: | , , , |
|---|---|
| Định dạng: | Journal article |
| Được phát hành: |
London Mathematical Society
2017
|
| Tóm tắt: | 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 |
|---|