Extensions of Bondy’s Theorem on Cycles in $2$-Connected Graphs.

Abstract

A simple, undirected $2$-connected graph $G$ of order $n$ belongs to the class $\mathcal{B}(n,\theta )$, $\theta \ge 0$ if $2(d(x)+d(y)+d(z))\ge 3(n–1–\theta )$ holds for all independent triples $\{x,y,z\}$ of vertices. It is known (Bondy’s theorem for $2$-connected graphs) that $G$ is hamiltonian if $\theta =0$. In this paper we give a full characterization of graphs $G$ in $\mathcal{B}(n,\theta )$, $\theta \le 2$ in terms of their dual hamiltonian closure.