Cookies

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.

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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
(340Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1016/j.dam.2016.08.011
Publisher statement:© 2016 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
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

Export:
Export
Look up in GoogleScholar