Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777143 | Electronic Notes in Discrete Mathematics | 2017 | 7 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Jaehoon Kim, Hong Liu, Maryam Sharifzadeh, Katherine Staden,