A feedback vertex set in a graph G is a vertex subset S such that \begin{document}$ G\setminus S $\end{document} 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 \begin{document}$ K_{3} $\end{document} or \begin{document}$ K_{4} $\end{document}. (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.
Zhong-Zheng Tang, Zhuo Diao
. Characterizing the Extremal k-Girth Graphs on Feedback Vertex Set[J]. Journal of the Operations Research Society of China, 2025
, 13(2)
: 515
-534
.
DOI: 10.1007/s40305-023-00483-3
[1] Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discret. Math. 12(3), 289-297 (1999)
[2] Erdös, P., Pósa, L.: On independent circuits contained in a graph. Can. J. Math. 17, 347-352 (1965)
[3] Even, G., Naor, J., Schieber, B., Sudan, M.: Approximating minimum feedback sets and multi-cuts in directed graphs. In: Balas, E., Clausen, J. (Eds.) Integer Programming and Combinatorial Optimization, 4th International (IPCO 1995) Conference, Copenhagen, Denmark, volume 920 of Lecture Notes in Computer Science. Springer, pp. 14-28 (1995)
[4] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)
[5] Reed, B.A., Robertson, N., Seymour, P.D., Thomas, R.: Packing directed circuits. Combinatorica 16(4), 535-554 (1996)
[6] Ren, H., Yang, C., Zhao, T.: A new formula for the decycling number of regular graphs. Discrete Math. 340(12), 3020-3031 (2017)
[7] Shi, L., Hongyu, X.: Large induced forests in graphs. J. Graph Theory 85(4), 759-779 (2017)
[8] Wang, T., Baoyindureng, W.: The size of graphs with given feedback vertex number. Discrete Appl. Math. 314, 213-222 (2022)
[9] Wang, T., Wu, B.: Maximum induced forests of product graphs. Bull. Malays. Math. Sci. Soc. 46(1), 7 (2023)
[10] Wang, Y., Xie, Q., Yu, X.: Induced forests in bipartite planar graphs. arXiv:1605.00047 (2016)
[11] Albertson, M.O., Berman, D.M.: A conjecture on planar graphs. Graph Theory Rel. Top. 357, 66 (1979)
[12] Borodin, O.V.: A proof of Grunbaum’s conjecture on the acyclic 5-colorability of planar graphs. In: Doklady Akademii Nauk, volume 231, pp. 18-20. Russian Academy of Sciences (1976)
[13] Alon, N., Mubayi, D., Thomas, R.: Large induced forests in sparse graphs. J. Graph Theory 38(3), 113-123 (2001)
[14] Dross, F., Montassier, M., Pinlou, A.: A lower bound on the order of the largest induced forest in planar graphs with high girth. Discrete Appl. Math. 214, 99-107 (2016)
[15] Kelly, T., Liu, C.-H.: Minimum size of feedback vertex sets of planar graphs of girth at least five. Eur. J. Combin. 61, 138-150 (2017)
[16] Kelly, T., Liu, C.-H.: Size of the largest induced forest in subcubic graphs of girth at least four and five. J. Graph Theory 89(4), 457-478 (2018)
[17] Bondy, J.A., Murty, U.S.R.: Graph Theory, Volume 244 of Graduate Texts in Mathematics. Springer (2008)
[18] Diestel, R.: Graph Theory, 4th Ed, Volume 173 of Graduate Texts in Mathematics. Springer (2012)
