The price of connectivity for feedback vertex set

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

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: Sep 17, 2017
• Journal: Discrete Applied Mathematics
• Print ISSN: 0166-218X
• Electronic ISSN: 1872-6771
• 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