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 \( \epsilon \) and given integers \( p \geq 2 \) and \( k \in \{2, 3\} \), the family of \( k \)-connected Hamiltonian claw-free graphs \( H \) of sufficiently large order \( n \) with \( \delta(H) \geq 3 \) and \( \delta_k(H) \geq t(n + \epsilon)/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 \( \epsilon \) for some \( t \geq 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 \leq t \leq 4 \)), if \( \delta_t(H) \geq \frac{n+1}{3} \) and \( \delta(H) \geq 3 \), then \( H \) is Hamiltonian.
• (b) For \( k = 3 \) and \( t = 3 \), (i) if \( \delta_3(H) \geq \frac{n+9}{10} \), then \( H \) is Hamiltonian; (ii) if \( \delta_2(H) \geq \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) \geq \frac{n+9}{8} \), then \( H \) is Hamiltonian; (ii) if \( \delta_3(H) \geq \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.