Proof of a conjecture of Bauer, Fan and Veldman

Abstract

For a 1-tough graph $G$ we define ${\sigma }_3(G)=\min \{°(u)+°(v)+°(w):$ $\{u,v,w\}$ is an independent set of vertices$\}$ and $NC2(G)=\min \{|N(u)\cup N(v)|:d(u,v)=2\}$. D. Bauer, G. Fan and H.J.Veldman proved that $c(G)\ge \min \{n,2NC2(G)\}$ for any 1-tough graph $G$ with ${\sigma }_3(G)\ge n\ge 3$, where $c(G)$ is the circumference of $G$ (D. Bauer, G. Fan and H.J.Veldman,Hamiltonian properties of graphs with large neighborhood unions,Discrete Mathematics, 1991). They also conjectured a stronger upper bound for the circumference: $c(G)\ge \min \{n,2NC2(G)+4\}$.In this paper, we prove this conjecture.

arXiv comment25 pages,5 figures