The price of connectivity for cycle transversals.

Abstract

For a family of graphs F, an F-transversal of a graph G is a subset S⊆V(G) that intersects every subset of V(G) that induces a subgraph isomorphic to a graph in F. Let tF(G) be the minimum size of an F-transversal of G, and View the MathML source be the minimum size of an F-transversal of G that induces a connected graph. For a class of connected graphs G, we say that the price of connectivity of F-transversals is multiplicative if, for all G∈G, View the MathML source is bounded by a constant, and additive if View the MathML source is bounded by a constant. The price of connectivity is identical if tF(G) and View the MathML source are always equal and unbounded if View the MathML source cannot be bounded in terms of tF(G). We study classes of graphs characterized by one forbidden induced subgraph H and F-transversals where F contains an infinite number of cycles and, possibly, also one or more anticycles or short paths. We determine exactly those classes of connected H-free graphs where the price of connectivity of these F-transversals is unbounded, multiplicative, additive, or identical. In particular, our tetrachotomies extend known results for the case when F is the family of all cycles.