Characterizing the Extremal k-Girth Graphs on Feedback Vertex Set

Abstract

A feedback vertex set in a graph G is a vertex subset S such that $G\setminus S$ is acyclic. The girth of a graph is the minimum cycle length in G. In this paper, some results are proven: (i) Every connected graph G has a feedback vertex set at most m/3 and the bound is tight if and only if G is $K_{3}$ or $K_{4}$. (ii) Alon et al. (J Graph Theory 38:113–123, 2001) proved every connected triangle-free graph G has a feedback vertex set at most m/4. We prove the bound is tight if and only if G is 4-cycle, Square-Claw or Double-Squares. (iii) Every connected outerplanar graph G with girth k has a feedback vertex set at most m/k and the bound is tight if and only if G is a k-cycle. This result verifies the conjecture of Dross et al. (Discrete Appl Math 214:99–107, 2016) on outerplanar graph.