Article ID Journal Published Year Pages File Type
420828 Discrete Applied Mathematics 2006 8 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,