Article ID Journal Published Year Pages File Type
4646938 Discrete Mathematics 2015 7 Pages PDF
Abstract

A set of vertices of a multigraph whose removal produces a forest is a feedback vertex set. For a connected cubic multigraph GG of order nn at least 9, we show the existence of a feedback vertex set of order at most 13(n+2ℓ+me+k4+), where ℓℓ is the number of loops of GG, meme is the number of multiple edges of GG, and k4+ is the number of submultigraphs of GG that arise from K4K4 by subdividing one edge. This bound is best possible and implies several known bounds.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,