Dominating Cycles in Triangle-Free Graphs

Abstract

A cycle \(C\) in a graph \(G\) is said to be dominating if \(E(G-C) = 0\). Enomoto et al. showed that if \(G\) is a 2-connected triangle-free graph with \(\alpha(G) \leq 2\kappa(G) – 2\), then every longest cycle is dominating. But it is unknown whether the condition on the independence number is sharp. In this paper, we show that if \(G\) is a 2-connected triangle-free graph with \(\alpha(G) \leq 2\kappa(G) – 1\), then \(G\) has a longest cycle which is dominating. This condition is best possible.