Fan type condition and characterization of Hamiltonian graphs
Authors:
Kewen Chao, Chunwei Song and Ping Zhang
Journal:
Proc. Amer. Math. Soc. 142 (2014), 23032311
MSC (2010):
Primary 05C45, 05C75; Secondary 05C07, 05C38
Published electronically:
March 28, 2014
MathSciNet review:
3195755
Fulltext 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 2connected 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 2connected 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 2connected 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
(87f:05106), 10.1112/jlms/s232.3.385
 [2]
A.
Benhocine and A.
P. Wojda, The GengHua Fan conditions for pancyclic or
Hamiltonconnected graphs, J. Combin. Theory Ser. B
42 (1987), no. 2, 167–180. MR 884252
(88f:05071), 10.1016/00958956(87)900384
 [3]
J.
A. Bondy and U.
S. R. Murty, Graph theory with applications, American Elsevier
Publishing Co., Inc., New York, 1976. MR 0411988
(54 #117)
 [4]
Reinhard
Diestel, Graph theory, 3rd ed., Graduate Texts in Mathematics,
vol. 173, SpringerVerlag, Berlin, 2005. MR 2159259
(2006e:05001)
 [5]
G.
A. Dirac, Some theorems on abstract graphs, Proc. London Math.
Soc. (3) 2 (1952), 69–81. MR 0047308
(13,856e)
 [6]
Genghua
Fan, New sufficient conditions for cycles in graphs, J.
Combin. Theory Ser. B 37 (1984), no. 3,
221–227. MR
769364 (86c:05083), 10.1016/00958956(84)900546
 [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 NPcompleteness;
A Series of Books in the Mathematical Sciences. MR 519066
(80g:68056)
 [8]
Ronald
J. Gould, Advances on the Hamiltonian problem—a survey,
Graphs Combin. 19 (2003), no. 1, 7–52. MR 1974368
(2004a:05092), 10.1007/s003730020492x
 [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
(2008g:05122), 10.1016/j.dam.2007.03.013
 [10]
Oystein
Ore, Note on Hamilton circuits, Amer. Math. Monthly
67 (1960), 55. MR 0118683
(22 #9454)
 [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
(96i:05001)
 [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, 385391. MR 825912 (87f:05106), http://dx.doi.org/10.1112/jlms/s232.3.385
 [2]
 A. Benhocine and A. P. Wojda, The GengHua Fan conditions for pancyclic or Hamiltonconnected graphs, J. Combin. Theory Ser. B 42 (1987), no. 2, 167180. MR 884252 (88f:05071), http://dx.doi.org/10.1016/00958956(87)900384
 [3]
 J. A. Bondy and U. S. R. Murty, Graph theory with applications, American Elsevier Publishing Co., Inc., New York, 1976. MR 0411988 (54 #117)
 [4]
 Reinhard Diestel, Graph theory, 3rd ed., Graduate Texts in Mathematics, vol. 173, SpringerVerlag, Berlin, 2005. MR 2159259 (2006e:05001)
 [5]
 G. A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. (3) 2 (1952), 6981. MR 0047308 (13,856e)
 [6]
 Genghua Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory Ser. B 37 (1984), no. 3, 221227. MR 769364 (86c:05083), http://dx.doi.org/10.1016/00958956(84)900546
 [7]
 Michael R. Garey and David S. Johnson, Computers and intractability, A guide to the theory of NPcompleteness. A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979. MR 519066 (80g:68056)
 [8]
 Ronald J. Gould, Advances on the Hamiltonian problema survey, Graphs Combin. 19 (2003), no. 1, 752. MR 1974368 (2004a:05092), http://dx.doi.org/10.1007/s003730020492x
 [9]
 Shengjia Li, Ruijuan Li, and Jinfeng Feng, An efficient condition for a graph to be Hamiltonian, Discrete Appl. Math. 155 (2007), no. 14, 18421845. MR 2354331 (2008g:05122), http://dx.doi.org/10.1016/j.dam.2007.03.013
 [10]
 Oystein Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960), 55. MR 0118683 (22 #9454)
 [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 (96i:05001)
Similar Articles
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 490085152
Email:
ping.zhang@wmich.edu
DOI:
http://dx.doi.org/10.1090/S000299392014119770
Keywords:
Hamiltonian,
Fan condition,
BenhocineWojda 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
