Pathkipas Ramsey numbers
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 G on p  vertices the following holds: either G G contains F  as a subgraph or the complement of G G contains H  as a subgraph. In this paper, we study the Ramsey numbers R ( P n , K ^ m ) , where Pn P n is a path on n  vertices and K ^ m is the graph obtained from the join of K1 K 1 and Pm P m . We determine the exact values of R ( P n , K ^ m ) for the following values of n and m : 1?n?5 1 ? n ? 5 and m?3 m ? 3 ; n?6 n ? 6 and (m  is odd, 3?m?2n-1 3 ? m ? 2 n - 1 ) or (m  is even, 4?m?n+1 4 ? m ? n + 1 ); 6?n?7 6 ? n ? 7 and m=2n-2 m = 2 n - 2 or m?2n m ? 2 n ; n?8 n ? 8 and m=2n-2 m = 2 n - 2 or m=2n m = 2 n or (qn-2q+1?m?qn-q+2 ( q  n - 2 q + 1 ? m ? q  n - q + 2 with 3?q?n-5) 3 ? q ? n - 5 ) or m?(n-3)2 m ? ( n - 3 ) 2 ; odd n?9 n ? 9 and (qn-3q+1?m?qn-2q ( q  n - 3 q + 1 ? m ? q  n - 2 q with 3?q?(n-3)/2) 3 ? q ? ( n - 3 ) / 2 ) or (qn-q-n+4?m?qn-2q ( q  n - q - n + 4 ? m ? q  n - 2 q with (n-1)/2?q?n-4) ( n - 1 ) / 2 ? q ? n - 4 ) . Moreover, we give lower bounds and upper bounds for R ( P n , K ^ m ) for the other values of m and n.
05c55 05d10