On the Ramsey Numbers for Trees versus Fans

The Ramsey number R(G, H) is the smallest number of vertices r such that any graph F with r vertices either contains G or its complement contains H. In this paper, we consider R(G, H) where G is a tree Tn of order n, and H is a fan F1,m=K1+Pm. Burr (1981) has provided the lower bound of R(Tn, F1,m). When m ≥ 2n-1, we give the better lower bound for R(Tn, F1,m). We also consider the Ramsey number of Tn versus F1,m for certain values of m when Tn is a tree with maximum degree n-5, n-4, or n-3. In particular, we determine R(Tn, F1,8) when Tn is a tree with maximum degree n-4 or n-5. We also proved that for a tree Tn with maximum degree n-3, the upper bound of R(Tn, F1,m) is R(Sn(1, 1), F1,m). Moreover, let x be a vertex with the maximum degree in Tn, and let Tn' be a tree that is constructed from Tn by deleting a pendant edge xu of Tn then connecting u to a pendant vertex of Tn. We show that R(Tn', F1,m) ≤ R(Tn, F1,m) for certain classes of Tn and Tn'.