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

Published electronically:
March 28, 2014

MathSciNet review:
3195755

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let be a simple graph of order . Ore's classical theorem states that if for each pair of nonadjacent vertices , then is Hamiltonian (*Amer. Math. Monthly* 67 (1960), 55). In 1984, Fan proved that if is 2-connected and for each pair of vertices with distance 2, then 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 is a 2-connected graph with independence number , and for each pair of vertices with distance 2, then is Hamiltonian with some exceptions: either is Hamiltonian or 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 is 2-connected and for each pair of vertices with distance 2, then either is Hamiltonian or is among certain classes of well characterized graphs. This extends previous results in the literature.

**[1]**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**, 10.1112/jlms/s2-32.3.385**[2]**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**, 10.1016/0095-8956(87)90038-4**[3]**J. A. Bondy and U. S. R. Murty,*Graph theory with applications*, American Elsevier Publishing Co., Inc., New York, 1976. MR**0411988****[4]**Reinhard Diestel,*Graph theory*, 3rd ed., Graduate Texts in Mathematics, vol. 173, Springer-Verlag, Berlin, 2005. MR**2159259****[5]**G. A. Dirac,*Some theorems on abstract graphs*, Proc. London Math. Soc. (3)**2**(1952), 69–81. MR**0047308****[6]**Genghua Fan,*New sufficient conditions for cycles in graphs*, J. Combin. Theory Ser. B**37**(1984), no. 3, 221–227. MR**769364**, 10.1016/0095-8956(84)90054-6**[7]**Michael R. Garey and David S. Johnson,*Computers and intractability*, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness; A Series of Books in the Mathematical Sciences. MR**519066****[8]**Ronald J. Gould,*Advances on the Hamiltonian problem—a survey*, Graphs Combin.**19**(2003), no. 1, 7–52. MR**1974368**, 10.1007/s00373-002-0492-x**[9]**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**, 10.1016/j.dam.2007.03.013**[10]**Oystein Ore,*Note on Hamilton circuits*, Amer. Math. Monthly**67**(1960), 55. MR**0118683**- [11]
Michael Sipser,
*Introduction to the theory of computation*, second ed., Course Technology, Cambridge, 2005. **[12]**Douglas B. West,*Introduction to graph theory*, Prentice Hall, Inc., Upper Saddle River, NJ, 1996. MR**1367739**

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

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

Email:
csong@math.pku.edu.cn

**Ping Zhang**

Affiliation:
Department of Mathematics, Western Michigan University, Kalamazoo, Michigan 49008-5152

Email:
ping.zhang@wmich.edu

DOI:
https://doi.org/10.1090/S0002-9939-2014-11977-0

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

Article copyright:
© Copyright 2014
American Mathematical Society