Characterizing the Extremal k-Girth Graphs on Feedback Vertex Set

A feedback vertex set in a graph G is a vertex subset S such that G \ 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.