Long Cycles in $2$-Connected Triangle-Free Graphs

Abstract

Dirac showed that a $2$-connected graph of order $n$ with minimum degree $\delta$ has circumference at least $min\{2\delta ,n\}$. We prove that a $2$-connected, triangle-free graph $G$ of order $n$ with minimum degree $\delta$ either has circumference at least $min\{4\delta –4,n\}$, or every longest cycle in $G$ is dominating. This result is best possible in the sense that there exist bipartite graphs with minimum degree $\delta$ whose longest cycles have length $4\delta –4$, and are not dominating.