Name
Abstract | ||
|---|---|---|
A set of vertices of a multigraph whose removal produces a forest is a feedback vertex set. For a connected cubic multigraph G of order n at least 9, we show the existence of a feedback vertex set of order at most 1 3 ( n + 2 ¿ + m e + k 4 + ) , where ¿ is the number of loops of G , m e is the number of multiple edges of G , and k 4 + is the number of submultigraphs of G that arise from K 4 by subdividing one edge. This bound is best possible and implies several known bounds. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.disc.2015.05.029 | Discrete Mathematics |
Keywords | Field | DocType |
Feedback vertex set,Induced forest | Discrete mathematics,Combinatorics,Multigraph,Vertex (geometry),Vertex (graph theory),Neighbourhood (graph theory),Multiple edges,Mathematics,Feedback vertex set | Journal |
Volume | Issue | ISSN |
338 | 12 | 0012-365X |
Citations | PageRank | References |
4 | 0.54 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Gentner | 1 | 22 | 4.46 |
| Dieter Rautenbach | 2 | 946 | 138.87 |