2015/10/09 by Rémy Belmonte, Pim van 't Hof, Belmonte, Rémy +6
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #Error Correcting Code Techniques #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1510.02639
arxiv created 2015/10/09 · openalex publication_date 2015/10/09 · arxiv updated 2015/10/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \cal G is defined as the maximum ratio cfvs(G)/fvs(G) over all connected graphs G∈ \cal G. We study the poc-fvs for graph classes defined by a finite family \cal H of forbidden induced subgraphs. We characterize exactly those finite families \cal H for which the poc-fvs for \cal H-free graphs is upper bounded by a constant. Additionally, for the case where |\cal H|=1, we determine exactly those graphs H for which there exists a constant cH such that cfvs(G)≤ fvs(G) + cH for every connected H-free graph G, as well as exactly those graphs H for which we can take cH=0.