Ore type condition and Hamiltonian graphs


Kewen Zhao




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.