Article ID Journal Published Year Pages File Type
4653225 European Journal of Combinatorics 2016 22 Pages PDF
Abstract

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

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,