Extremal problems on the Hamiltonicity of claw-free graphs

Abstract

In 1962, Erdős proved that if a graph $G$ with $n$ vertices satisfies $$e(G)>\max \left\{\left(\genfrac{}{}{0ex}{}{n-k}{2}\right)+k^2,\left(\genfrac{}{}{0ex}{}{\lceil (n+1)/2\rceil }{2}\right)+{\lfloor \frac{n-1}{2}\rfloor }^2\right\},$$ where the minimum degree $\hat{I}´(G)\ge k$ and $1\le k\le (n-1)/2$, then it is Hamiltonian. For $n\ge 2k+1$, let $E_n^k=K_k\vee (k{K}_1+K_{n-2k})$, where "$\vee$" is the "join" operation. One can observe $e(E_n^k)=\left(\genfrac{}{}{0ex}{}{n-k}{2}\right)+k^2$ and $E_n^k$ is not Hamiltonian. As $E_n^k$ contains induced claws for $k\ge 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.

22 pages, 8 figures, to appear in Discrete Mathematics