کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646983 | 1342321 | 2016 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An edge variant of the Erdős–Pósa property
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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
Journal: Discrete Mathematics - Volume 339, Issue 8, 6 August 2016, Pages 2027–2035
نویسندگان
Jean-Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos,