کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651057 | 1632445 | 2007 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The Path Partition Conjecture is true for claw-free graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The Path Partition Conjecture is true for claw-free graphs The Path Partition Conjecture is true for claw-free graphs](/preview/png/4651057.png)
چکیده انگلیسی
The detour order of a graph GG, denoted by τ(G)τ(G), is the order of a longest path in GG. The Path Partition Conjecture (PPC) is the following: If GG is any graph and (a,b)(a,b) any pair of positive integers such that τ(G)=a+bτ(G)=a+b, then the vertex set of GG has a partition (A,B)(A,B) such that τ(〈A〉)⩽aτ(〈A〉)⩽a and τ(〈B〉)⩽bτ(〈B〉)⩽b. We prove that this conjecture is true for the class of claw-free graphs. We also show that to prove that the PPC is true, it is sufficient to consider the class of 2-connected graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issues 11–12, 28 May 2007, Pages 1285–1290
Journal: Discrete Mathematics - Volume 307, Issues 11–12, 28 May 2007, Pages 1285–1290
نویسندگان
J.E. Dunbar, M. Frick,