Abstract In 1960, Ore proved that if $G$ is a graph
of order $n\geq3$ such that $d(x)+d(y)\geq n$ for each pair of
nonadjacent vertices $x,y$ in $G$, then $G$ is Hamiltonian. In
1985, Ainouche and Christofides proved that if $G$ is a 2-connected
graph of order $n\geq 3$ such that $d(x)+d(y)\geq n-1$ for each
pair of nonadjacent vertices $x,y$ in $G$, then $G$ is Hamiltonian
or $G$ belongs to two classes of exceptional graphs. In this
paper, we prove that if $G$ is a connected graph of order $n\geq
3$ such that $d(x)+d(y)\geq n-2$ for each pair of nonadjacent
vertices $x,y$ in $G$, then $G$ is Hamiltonian or $G$ belongs to
one of several classes of well-structured graphs.
|