A Generalization of Dirac’s Theorem for Claw-free Graphs

Abstract

For a graph $H$, let ${\delta }_t(H)=min\{|\bigcup _{i=1}^t{N}_H(v_i)|:|v_1,\dots ,v_t|\text{ are }t\text{ vertices in }H\}$. We show that for a given number $ϵ$ and given integers $p\ge 2$ and $k\in \{2,3\}$, the family of $k$-connected Hamiltonian claw-free graphs $H$ of sufficiently large order $n$ with $\delta (H)\ge 3$ and ${\delta }_k(H)\ge t(n+ϵ)/p$ has a finite obstruction set in which each member is a $k$-edge-connected $K_3$-free graph of order at most $max\{p/t+2t,3p/t+2t–7\}$ and without spanning closed trails. We found the best possible values of $p$ and $ϵ$ for some $t\ge 2$ when the obstruction set is empty or has the Petersen graph only. In particular, we prove the following for such graphs $H$:

• (a) For $k=2$ and a given $t$ ($1\le t\le 4$), if ${\delta }_t(H)\ge \frac{n+1}{3}$ and $\delta (H)\ge 3$, then $H$ is Hamiltonian.
• (b) For $k=3$ and $t=3$, (i) if ${\delta }_3(H)\ge \frac{n+9}{10}$, then $H$ is Hamiltonian; (ii) if ${\delta }_2(H)\ge \frac{n+9}{10}$, then either $H$ is Hamiltonian, or $H$ can be characterized by the Petersen graph.
• (c) For $k=3$ and $t=3$, (i) if ${\delta }_3(H)\ge \frac{n+9}{8}$, then $H$ is Hamiltonian; (ii) if ${\delta }_3(H)\ge \frac{n+6}{9}$, then either $H$ is Hamiltonian, or $H$ can be characterized by the Petersen graph.

These bounds on ${\delta }_t(H)$ are sharp. Since the number of graphs of orders at most $max\{p/t+2t,3p/t+2t–7\}$ is finite for given $p$ and $t$, improvements to (a), (b), or (c) by increasing the value of $p$ are possible with the help of a computer.