Fan type condition and characterization of Hamiltonian graphs

Abstract:

Let $G$ be a simple graph of order $n \geq 3$. Ore’s classical theorem states that if $d(x) + d(y) \geq n$ for each pair of nonadjacent vertices $x, y \in V(G)$, then $G$ is Hamiltonian (Amer. Math. Monthly 67 (1960), 55). In 1984, Fan proved that if $G$ is 2-connected and $\operatorname {max} \{ d(x), d(y) \} \geq n/2$ for each pair of vertices $x, y$ with distance 2, then $G$ is Hamiltonian. Fan’s result is a significant improvement to Ore’s theorem, and the condition stated is called Fan’s condition. Then in 1987, Benhocine and Wojda showed that if $G$ is a 2-connected graph with independence number $\alpha (G) \leq n/2$, and $\operatorname {max} \{ d(x), d(y) \} \geq \frac {n-1}{2}$ for each pair of vertices $x, y$ with distance 2, then $G$ is Hamiltonian with some exceptions: either $G$ is Hamiltonian or $G$ belongs to one of two classes of well characterized graphs. In 2007, Li et al. removed the independence restriction, but they also reversed the Fan type bigger degree lower bound condition to the stronger Ore type degree sum requirement.

In our present work, we drop the independence restriction while keeping Benhocine and Wojda’s relaxed Fan type condition to prove that if $G$ is 2-connected and $\operatorname {max} \{ d(x), d(y) \} \geq \frac {n-1}{2}$ for each pair of vertices $x, y$ with distance 2, then either $G$ is Hamiltonian or $G$ is among certain classes of well characterized graphs. This extends previous results in the literature.