Two sufficient conditions for the existence of Hamilton cycles in graphs

Bo Ning, Bing Chen, Shenggui Zhang

Published 2012-09-18, updated 2013-01-04Version 4

Let $G$ be a graph on $n\geq 3$ vertices, claw the bipartite graph $K_{1,3}$, and $Z_i$ the graph obtained from a triangle by attaching a path of length $i$ to its one vertex. $G$ is called 1-heavy if at least one end vertex of each induced claw of $G$ has degree at least $n/2$, and claw-\emph{o}-heavy if each induced claw of it has a pair of end vertices with degree sum at least $n$. In this paper we prove two results: (1) Every 2-connected claw-$o$-heavy graph $G$ is Hamiltonian if every pair of vertices $u,v$ in a subgraph $H\cong Z_1$ contained in an induced subgraph $Z_2$ of $G$ with $d_{H}(u,v)=2$ satisfies one of the following conditions: ($a$) $|N(u)\cap N(v)|\geq 2$; ($b$) $\max(d(u),d(v))\geq n/2$. (2) Every 3-connected 1-heavy graph $G$ is Hamiltonian if every pair of vertices $u,v$ in an induced subgraph $H\cong Z_2$ of $G$ with $d_{H}(u,v)=2$ satisfies one of the following conditions: ($a$) $|N(u)\cap N(v)|\geq 2$; ($b$) $\max(d(u),d(v))\geq n/2$. Our results improve or extend previous theorems of Broersma et al., Chen et al., Fan, Goodman & Hedetniemi, Gould & Jacobson and Shi on the existence of Hamilton cycles in graphs.