The price of connectivity for feedback vertex set

摘要

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. The price of connectivity for feedback vertex set (poc-fvs) for a class of graphs g is defined as the maximum ratio cfvs(G)/fvs(G) over all connected graphs G is an element of 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 vertical bar H vertical bar= 1, we determine exactly those graphs H for which there exists a constant CH 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. (C) 2016 Elsevier B.V. All rights reserved.