Ore type condition and Hamiltonian graphs

Abstract

In 1960, Ore proved that if $G$ is a graphof order $n\ge 3$ such that $d(x)+d(y)\ge n$ for each pair ofnonadjacent vertices $x,y$ in $G$, then $G$ is Hamiltonian. In1985, Ainouche and Christofides proved that if $G$ is a 2-connectedgraph of order $n\ge 3$ such that $d(x)+d(y)\ge n-1$ for eachpair of nonadjacent vertices $x,y$ in $G$, then $G$ is Hamiltonianor $G$ belongs to two classes of exceptional graphs. In thispaper, we prove that if $G$ is a connected graph of order $n\ge 3$ such that $d(x)+d(y)\ge n-2$ for each pair of nonadjacentvertices $x,y$ in $G$, then $G$ is Hamiltonian or $G$ belongs toone of several classes of well-structured graphs.