Extremal problems on the Hamiltonicity of claw-free graphs |
| |
Authors: | Binlong Li Bo Ning Xing Peng |
| |
Affiliation: | 1. Department of Applied Mathematics, Northwestern Polytechnical University, Xi’an, Shaanxi, 710072, PR China;2. Center for Applied Mathematics, Tianjin University, Tianjin, 300072, PR China |
| |
Abstract: | In 1962, Erd?s proved that if a graph with vertices satisfies where the minimum degree and , then it is Hamiltonian. For , let , where “” is the “join” operation. One can observe and is not Hamiltonian. As contains induced claws for , 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. |
| |
Keywords: | Hamilton cycles Claw-free graph Clique number Claw-free closure Eigenvalues |
本文献已被 ScienceDirect 等数据库收录! |
|