کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653225 | 1632759 | 2016 | 22 صفحه PDF | دانلود رایگان |
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.
Journal: European Journal of Combinatorics - Volume 58, November 2016, Pages 203–224