Skip to main content

Research Repository

Advanced Search

The price of connectivity for feedback vertex set

Belmonte, R.; Hof, van 't P.; Kaminski, M.; Paulusma, D.

Authors

R. Belmonte

van 't P. Hof

M. Kaminski



Contributors

Jaroslav Nešetřil
Editor

Marco Pellegrini
Editor

Abstract

Let fvs(G) and cfvs(G) denote the cardinalities of a minimum feedback vertex set and a minimum connected feedback vertex set of a graph G, respectively. In general graphs, the ratio cfvs(G)/fvs(G) can be arbitrarily large. We study the interdependence between fvs(G) and cfvs(G) in graph classes defined by excluding one induced subgraph H. We show that the ratio cfvs(G)/fvs(G) is bounded by a constant for every connected H-free graph G if and only if H is a linear forest. We also determine exactly those graphs H for which there exists a constant c H such that cfvs(G) ≤ fvs(G) + c H for every connected H-free graph G, as well as exactly those graphs H for which we can take c H = 0.

Citation

Belmonte, R., Hof, V. '. P., Kaminski, M., & Paulusma, D. (2013). The price of connectivity for feedback vertex set. In J. Nešetřil, & M. Pellegrini (Eds.), The seventh European conference on combinatorics, graph theory and applications (123-128). https://doi.org/10.1007/978-88-7642-475-5_20

Conference Name 7th European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2013
Conference Location Pisa, Italy
Publication Date Jan 1, 2013
Deposit Date Dec 20, 2014
Publisher Scuola Normale Superiore
Pages 123-128
Series Title Publications of the Scuola Normale Superiore
Series Number 16
Book Title The seventh European conference on combinatorics, graph theory and applications.
ISBN 9788876424748
DOI https://doi.org/10.1007/978-88-7642-475-5_20
Public URL https://durham-repository.worktribe.com/output/1154651


You might also like



Downloadable Citations