کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420828 | 683987 | 2006 | 8 صفحه PDF | دانلود رایگان |
For two given graphs FF and HH, the Ramsey number R(F,H)R(F,H) is the smallest positive integer pp such that for every graph GG on pp vertices the following holds: either GG contains FF as a subgraph or the complement of GG contains HH as a subgraph. In this paper, we study the Ramsey numbers R(Pn,Fm)R(Pn,Fm), where PnPn is a path on nn vertices and FmFm is the graph obtained from mm disjoint triangles by identifying precisely one vertex of every triangle (FmFm is the join of K1K1 and mK2mK2). We determine the exact values of R(Pn,Fm)R(Pn,Fm) for the following values of nn and mm: 1⩽n⩽51⩽n⩽5 and m⩾2m⩾2; n⩾6n⩾6 and 2⩽m⩽(n+1)/22⩽m⩽(n+1)/2; 6⩽n⩽76⩽n⩽7 and m⩾n-1m⩾n-1; n⩾8n⩾8 and n-1⩽m⩽nn-1⩽m⩽n or ((q·n-2q+1)/2⩽m⩽(q·n-q+2)/2((q·n-2q+1)/2⩽m⩽(q·n-q+2)/2 with 3⩽q⩽n-5)3⩽q⩽n-5) or m⩾(n-3)2/2m⩾(n-3)2/2; odd n⩾9n⩾9 and ((q·n-3q+1)/2⩽m⩽(q·n-2q)/2((q·n-3q+1)/2⩽m⩽(q·n-2q)/2 with 3⩽q⩽(n-3)/2)3⩽q⩽(n-3)/2) or ((q·n-q-n+4)/2⩽m⩽(q·n-2q)/2((q·n-q-n+4)/2⩽m⩽(q·n-2q)/2 with (n-1)/2⩽q⩽n-5)(n-1)/2⩽q⩽n-5). Moreover, we give nontrivial lower bounds and upper bounds for R(Pn,Fm)R(Pn,Fm) for the other values of mm and nn.
Journal: Discrete Applied Mathematics - Volume 154, Issue 9, 1 June 2006, Pages 1429–1436