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
Abstract | References | Similar Articles | Additional Information
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.
- 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 https://doi.org/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 https://doi.org/10.1016/0095-8956%2887%2990038-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 https://doi.org/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 https://doi.org/10.1016/0095-8956%2884%2990054-6
- 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
- Ronald J. Gould, Advances on the Hamiltonian problem—a survey, Graphs Combin. 19 (2003), no. 1, 7–52. MR 1974368, DOI https://doi.org/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 https://doi.org/10.1016/j.dam.2007.03.013
- Oystein Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960), 55. MR 118683, DOI https://doi.org/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
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
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
Article copyright:
© Copyright 2014
American Mathematical Society