کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651161 1632447 2007 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On Ramsey numbers for paths versus wheels
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On Ramsey numbers for paths versus wheels
چکیده انگلیسی

For two given graphs F and H  , the Ramsey number R(F,H)R(F,H) is the smallest positive integer p such that for every graph G on p vertices the following holds: either G contains F as a subgraph or the complement of G contains H   as a subgraph. In this paper, we study the Ramsey numbers R(Pn,Wm)R(Pn,Wm), where PnPn is a path on n   vertices and WmWm is the graph obtained from a cycle on m   vertices by adding a new vertex and edges joining it to all the vertices of the cycle. We present the exact values of R(Pn,Wm)R(Pn,Wm) for the following values of n and m  : n=1,2,3n=1,2,3 or 5 and m⩾3m⩾3; n=4n=4 and m=3,4,5m=3,4,5 or 7; n⩾6n⩾6 and (m   is odd, 3⩽m⩽2n-13⩽m⩽2n-1) or (m   is even, 4⩽m⩽n+14⩽m⩽n+1); odd n⩾7n⩾7 and m=2n-2m=2n-2 or m=2nm=2n or m⩾(n-3)2m⩾(n-3)2; odd n⩾9n⩾9 and q·n-2q+1⩽m⩽q·n-q+2q·n-2q+1⩽m⩽q·n-q+2 with 3⩽q⩽n-53⩽q⩽n-5. Moreover, we give nontrivial lower bounds and upper bounds for R(Pn,Wm)R(Pn,Wm) for the other values of m and n.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issues 7–8, 6 April 2007, Pages 975–982
نویسندگان
, ,