Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646938 | Discrete Mathematics | 2015 | 7 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Michael Gentner, Dieter Rautenbach,