Name
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.endm.2017.07.029 | Electronic Notes in Discrete Mathematics |
Keywords | DocType | Volume |
Extremal graph theory,Hamiltonian cycles,expansion,Blow-up method | Journal | 61 |
Issue | ISSN | Citations |
5 | 1571-0653 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jae-Hoon Kim | 1 | 268 | 65.73 |
| Hong Liu | 2 | 39 | 8.54 |
| Maryam Sharifzadeh | 3 | 11 | 3.83 |
| Katherine Staden | 4 | 6 | 3.31 |