Proof of Komlos's conjecture on Hamiltonian subsets

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 78
  • Download : 0
Komlos 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.
Publisher
WILEY
Issue Date
2017-11
Language
English
Article Type
Article
Citation

PROCEEDINGS OF THE LONDON MATHEMATICAL SOCIETY, v.115, pp.974 - 1013

ISSN
0024-6115
DOI
10.1112/plms.12059
URI
http://hdl.handle.net/10203/263344
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0