Skip to main content

Research Repository

Advanced Search

The price of connectivity for feedback vertex set

Belmonte, R.; van ’t Hof, P.; Kamiński, M.; Paulusma, D.

The price of connectivity for feedback vertex set Thumbnail


Authors

R. Belmonte

P. van ’t Hof

M. Kamiński



Abstract

Let View the MathML source and View the MathML source denote the cardinalities of a minimum feedback vertex set and a minimum connected feedback vertex set of a graph G, respectively. The price of connectivity for feedback vertex set (poc-fvs) for a class of graphs G is defined as the maximum ratio View the MathML source over all connected graphs G∈G. We study the poc-fvs for graph classes defined by a finite family H of forbidden induced subgraphs. We characterize exactly those finite families H for which the poc-fvs for H-free graphs is upper bounded by a constant. Additionally, for the case where ∣H∣=1, we determine exactly those graphs H for which there exists a constant cH such that View the MathML source for every connected H-free graph G, as well as exactly those graphs H for which we can take cH=0.

Citation

Belmonte, R., van ’t Hof, P., Kamiński, M., & Paulusma, D. (2017). The price of connectivity for feedback vertex set. Discrete Applied Mathematics, 217(Part B), 132-143. https://doi.org/10.1016/j.dam.2016.08.011

Journal Article Type Article
Acceptance Date Aug 16, 2016
Online Publication Date Sep 17, 2016
Publication Date Jan 30, 2017
Deposit Date Oct 1, 2016
Publicly Available Date Mar 29, 2024
Journal Discrete Applied Mathematics
Print ISSN 0166-218X
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 217
Issue Part B
Pages 132-143
DOI https://doi.org/10.1016/j.dam.2016.08.011
Public URL https://durham-repository.worktribe.com/output/1375259

Files





You might also like



Downloadable Citations