A feedback vertex set in a graph G\S is a vertex subset S such that 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 vert...A feedback vertex set in a graph G\S is a vertex subset S such that 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)orK_(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.展开更多
基金supported by the National Natural Science Foundation of China(Nos.11901605,12101069)the disciplinary funding of Central University of Finance and Economics,the Emerging Interdisciplinary Project of CUFE.
文摘A feedback vertex set in a graph G\S is a vertex subset S such that 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)orK_(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.
