کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4656806 | 1632983 | 2015 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The structure of graphs not admitting a fixed immersion
ترجمه فارسی عنوان
ساختار گراف هایی که یک غوطه ور ثابت را نمی پذیرند
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
غوطه وری، لبه مجزا، تجزیه درختان، تجزیه درختان برش
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We present an easy structure theorem for graphs which do not admit an immersion of the complete graph KtKt. The theorem motivates the definition of a variation of tree decompositions based on edge cuts instead of vertex cuts which we call tree-cut decompositions. We give a definition for the width of tree-cut decompositions, and using this definition along with the structure theorem for excluded clique immersions, we prove that every graph either has bounded tree-cut width or admits an immersion of a large wall.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 110, January 2015, Pages 47–66
Journal: Journal of Combinatorial Theory, Series B - Volume 110, January 2015, Pages 47–66
نویسندگان
Paul Wollan,