کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651161 | 1632447 | 2007 | 8 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Mathematics - Volume 307, Issues 7–8, 6 April 2007, Pages 975–982