The price of connectivity for cycle transversals. (November 2016) - Hartinger, Tatiana R.; Johnson, Matthew; Milanič, Martin; Paulusma, Daniël
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 t F ( G )  be the minimum size of an F -transversal of G, and ct F ( G )  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, ct F ( G ) / t F ( G ) is bounded by a constant, and additive if ct F ( G ) − t F ( G ) is bounded by a constant. The price of connectivity is identical if t F ( G )  and ct F ( G )  are always equal and unbounded if ct F ( G )  cannot be bounded in terms of t F ( 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.