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.

Keywords: Ore type condition; Hamiltonian graphs.

MSC: 05C38, 05C45

Pages:  412$-$418     

Volume  65 ,  Issue  3 ,  2013