Skip to Main Content

Proceedings of the American Mathematical Society

Published by the American Mathematical Society, the Proceedings of the American Mathematical Society (PROC) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Proceedings of the American Mathematical Society is 0.85.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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
Similar Articles
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