Relaxations of Ore's Condition on Cycles

Abstract

A simple, undirected $2$-connected graph $G$ of order $n$ belongs to class ${\cal O}(n$,$\varphi)$, $\varphi\geq0$, if $\sigma_{2}=n-\varphi.$ It is well known (Ore's theorem) that $G$ is hamiltonian if $\varphi= 0$, in which case the $2$-connectedness hypothesis is implied. In this paper we provide a method for studying this class of graphs. As an application we give a full characterization of graphs $G$ in ${\cal O}(n$,$\varphi)$, $\varphi\leq3$, in terms of their dual hamiltonian closure.