The price of connectivity for cycle transversals. (November 2016)

• Record Type: Journal Article
• Authors: Hartinger, Tatiana R.; Johnson, Matthew; Milanič, Martin; Paulusma, Daniël
• Is Part Of: European journal of combinatorics. Volume 58(2016:Nov.)
• Page Start: 203
• Page End: 224
• Publication Date: 2016-11
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2016.06.003
• Languages: English
• ISSNs: 0195-6698

Abstract

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.