## Fan type condition and characterization of Hamiltonian graphs

HTML articles powered by AMS MathViewer

- by Kewen Chao, Chunwei Song and Ping Zhang PDF
- Proc. Amer. Math. Soc.
**142**(2014), 2303-2311 Request permission

## 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.

## References

- Ahmed Ainouche and Nicos Christofides,
*Conditions for the existence of Hamiltonian circuits in graphs based on vertex degrees*, J. London Math. Soc. (2)**32**(1985), no. 3, 385–391. MR**825912**, DOI 10.1112/jlms/s2-32.3.385 - A. Benhocine and A. P. Wojda,
*The Geng-Hua Fan conditions for pancyclic or Hamilton-connected graphs*, J. Combin. Theory Ser. B**42**(1987), no. 2, 167–180. MR**884252**, DOI 10.1016/0095-8956(87)90038-4 - J. A. Bondy and U. S. R. Murty,
*Graph theory with applications*, American Elsevier Publishing Co., Inc., New York, 1976. MR**0411988** - Reinhard Diestel,
*Graph theory*, 3rd ed., Graduate Texts in Mathematics, vol. 173, Springer-Verlag, Berlin, 2005. MR**2159259** - G. A. Dirac,
*Some theorems on abstract graphs*, Proc. London Math. Soc. (3)**2**(1952), 69–81. MR**47308**, DOI 10.1112/plms/s3-2.1.69 - Genghua Fan,
*New sufficient conditions for cycles in graphs*, J. Combin. Theory Ser. B**37**(1984), no. 3, 221–227. MR**769364**, DOI 10.1016/0095-8956(84)90054-6 - Michael R. Garey and David S. Johnson,
*Computers and intractability*, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness. MR**519066** - Ronald J. Gould,
*Advances on the Hamiltonian problem—a survey*, Graphs Combin.**19**(2003), no. 1, 7–52. MR**1974368**, DOI 10.1007/s00373-002-0492-x - Shengjia Li, Ruijuan Li, and Jinfeng Feng,
*An efficient condition for a graph to be Hamiltonian*, Discrete Appl. Math.**155**(2007), no. 14, 1842–1845. MR**2354331**, DOI 10.1016/j.dam.2007.03.013 - Oystein Ore,
*Note on Hamilton circuits*, Amer. Math. Monthly**67**(1960), 55. MR**118683**, DOI 10.2307/2308928 - Michael Sipser,
*Introduction to the theory of computation*, second ed., Course Technology, Cambridge, 2005. - Douglas B. West,
*Introduction to graph theory*, Prentice Hall, Inc., Upper Saddle River, NJ, 1996. MR**1367739**

## Additional Information

**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
- 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
- © Copyright 2014 American Mathematical Society
- 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
- MathSciNet review: 3195755