کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4646983 1342321 2016 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An edge variant of the Erdős–Pósa property
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
An edge variant of the Erdős–Pósa property
چکیده انگلیسی

For every  r∈Nr∈N, we denote by θrθr the multigraph with two vertices and rr parallel edges. Given a graph GG, we say that a subgraph HH of GG is a model of  θrθrin  GG if HH contains θrθr as a contraction. We prove that the following edge variant of the Erdős–Pósa property holds for every r⩾2r⩾2: if GG is a graph and kk is a positive integer, then either GG contains a packing of kk mutually edge-disjoint models of θrθr, or it contains a set SS of fr(k)fr(k) edges such that G∖SG∖S has no θrθr-model, for both fr(k)=O(k2r3polylogkr)fr(k)=O(k2r3polylogkr) and fr(k)=O(k4r2polylogkr)fr(k)=O(k4r2polylogkr).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 8, 6 August 2016, Pages 2027–2035
نویسندگان
, , ,