×

Relaxations of Ore’s condition on cycles. (English) Zbl 1096.05031

Summary: A simple, undirected \(2\)-connected graph \(G\) of order \(n\) belongs to class \({\mathcal 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 \({\mathcal O}(n\),\(\varphi)\), \(\varphi\leq3\), in terms of their dual Hamiltonian closure.

MSC:

05C45 Eulerian and Hamiltonian graphs