On Relative Length of Long Paths and Cycles in Graphs

Abstract

Let $G$ be a graph on $n$ vertices, $p$ the order of a longest path and $\kappa$ the connectivity of $G$. In 1989, Bauer, Broersma Li and Veldman proved that if $G$ is a 2-connected graph with $d(x)+d(y)+d(z)\ge n+\kappa$ for all triples $x,y,z$ of independent vertices, then $G$ is hamiltonian. In this paper we improve this result by reducing the lower bound $n+\kappa$ to $p+\kappa$.

arXiv comment8 pages