   ISSN 1088-6826(online) ISSN 0002-9939(print)

Fan type condition and characterization of Hamiltonian graphs

Authors: Kewen Chao, Chunwei Song and Ping Zhang
Journal: Proc. Amer. Math. Soc. 142 (2014), 2303-2311
MSC (2010): Primary 05C45, 05C75; Secondary 05C07, 05C38
DOI: https://doi.org/10.1090/S0002-9939-2014-11977-0
Published electronically: March 28, 2014
MathSciNet review: 3195755
Full-text PDF Free Access

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.

[Enhancements On Off] (What's this?)

References

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05C45, 05C75, 05C07, 05C38

Retrieve articles in all journals with MSC (2010): 05C45, 05C75, 05C07, 05C38

Kewen Chao
Affiliation: Department of Mathematics, Qiongzhou University, Sanya, Hainan 572022, People’s Republic of China
Email: kewen@bxemail.com

Chunwei Song
Affiliation: School of Mathematical Sciences, and LMAM, Peking University, Beijing 100871, People’s Republic of China
MR Author ID: 771186
Email: csong@math.pku.edu.cn

Ping Zhang
Affiliation: Department of Mathematics, Western Michigan University, Kalamazoo, Michigan 49008-5152
Email: ping.zhang@wmich.edu

Keywords: Hamiltonian, Fan condition, Benhocine-Wojda condition, Ore condition
Received by editor(s): August 26, 2011
Received by editor(s) in revised form: July 26, 2012
Published electronically: March 28, 2014
Additional Notes: The first author was supported in part by Science Foundation of Hainan Province Grant #10501.
The second author was supported in part by 973 Program Grant #2013CB834201 and NSFC Grant #11101009.
Communicated by: Jim Haglund