Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8902862 | Discrete Mathematics | 2018 | 15 Pages |
Abstract
In 1962, ErdÅs proved that if a graph G with n vertices satisfies e(G)>maxnâk2+k2,â(n+1)â2â2+nâ122,where the minimum degree δ(G)â¥k and 1â¤kâ¤(nâ1)â2, then it is Hamiltonian. For nâ¥2k+1, let Enk=Kkâ¨(kK1+Knâ2k), where “⨔ is the “join” operation. One can observe e(Enk)=nâk2+k2 and Enk is not Hamiltonian. As Enk contains induced claws for kâ¥2, a natural question is to characterize all 2-connected claw-free non-Hamiltonian graphs with the largest possible number of edges. We answer this question completely by proving a claw-free analog of ErdÅs' theorem. Moreover, as byproducts, we establish several tight spectral conditions for a 2-connected claw-free graph to be Hamiltonian. Similar results for the traceability of connected claw-free graphs are also obtained. Our tools include RyjáÄek's claw-free closure theory and Brousek's characterization of minimal 2-connected claw-free non-Hamiltonian graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Binlong Li, Bo Ning, Xing Peng,