We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

The price of connectivity for feedback vertex set.

Belmonte, R. and van ’t Hof, P. and Kamiński, M. and Paulusma, D. (2017) 'The price of connectivity for feedback vertex set.', Discrete applied mathematics., 217 (Part B). pp. 132-143.


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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
Publisher Web site:
Publisher statement:© 2016 This manuscript version is made available under the CC-BY-NC-ND 4.0 license
Date accepted:16 August 2016
Date deposited:03 October 2016
Date of first online publication:17 September 2016
Date first made open access:17 September 2017

Save or Share this output

Look up in GoogleScholar