Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420929 | Discrete Applied Mathematics | 2007 | 7 Pages |
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 GG on p vertices the following holds: either GG contains F as a subgraph or the complement of GG contains H as a subgraph. In this paper, we study the Ramsey numbers R(Pn,K^m), where PnPn is a path on n vertices and K^m is the graph obtained from the join of K1K1 and PmPm. We determine the exact values of R(Pn,K^m) for the following values of n and m : 1⩽n⩽51⩽n⩽5 and m⩾3m⩾3; 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); 6⩽n≤76⩽n≤7 and m=2n-2m=2n-2 or m⩾2nm⩾2n; n⩾8n⩾8 and m=2n-2m=2n-2 or m=2nm=2n or (q·n-2q+1⩽m⩽q·n-q+2(q·n-2q+1⩽m⩽q·n-q+2 with 3⩽q⩽n-5)3⩽q⩽n-5) or m⩾(n-3)2m⩾(n-3)2; odd n⩾9n⩾9 and (q·n-3q+1⩽m⩽q·n-2q(q·n-3q+1⩽m⩽q·n-2q with 3⩽q⩽(n-3)/2)3⩽q⩽(n-3)/2) or (q·n-q-n+4⩽m⩽q·n-2q(q·n-q-n+4⩽m⩽q·n-2q with (n-1)/2⩽q⩽n-4)(n-1)/2⩽q⩽n-4). Moreover, we give lower bounds and upper bounds for R(Pn,K^m) for the other values of m and n.