Ore type condition and Hamiltonian graphs
Keywords:
Ore type condition, Hamiltonian graphsSubjects:
05C38, 05C45Abstract
In 1960, Ore proved that if $G$ is a graphof order $n\geq3$ such that $d(x)+d(y)\geq 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\geq 3$ such that $d(x)+d(y)\geq 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\geq3$ such that $d(x)+d(y)\geq 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.
Downloads
Published
Issue
Section
License
Copyright (c) 2013 Authors retain copyright to their work.
This work is licensed under a Creative Commons Attribution 4.0 International License.