کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903851 | 1632962 | 2018 | 32 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The ErdÅs-Pósa property for edge-disjoint immersions in 4-edge-connected graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A graph H is immersed in a graph G if the vertices of H are mapped to distinct vertices of G, and the edges of H are mapped to paths joining the corresponding pairs of vertices of G, in such a way that the paths are pairwise edge-disjoint. In this paper, we show that the ErdÅs-Pósa property holds for packing edge-disjoint Kt-immersions in 4-edge-connected graphs. More precisely, for positive integers k and t, there exists a constant f(k,t) such that a 4-edge-connected graph G has either k edge-disjoint Kt-immersions, or an edge subset F of size at most f(k,t) such that GâF has no Kt-immersion. The 4-edge-connectivity in this statement is best possible in the sense that 3-edge-connected graphs do not have the ErdÅs-Pósa property.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 131, July 2018, Pages 138-169
Journal: Journal of Combinatorial Theory, Series B - Volume 131, July 2018, Pages 138-169
نویسندگان
Naonori Kakimura, Ken-ichi Kawarabayashi,