کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4653225 1632759 2016 22 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The price of connectivity for cycle transversals
ترجمه فارسی عنوان
قیمت قابلیت اتصال برای transvertals چرخه
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 58, November 2016, Pages 203–224
نویسندگان
, , , ,