Ramsey numbers of trees versus fans.

For two given graphs G 1 and G 2 , the Ramsey number R ( G 1 , G 2 ) is the smallest integer N such that, for any graph G of order N , either G contains G 1 as a subgraph or the complement of G contains G 2 as a subgraph. Let T n be a tree of order n , S n a star of order n , and F m a fan of order 2 m + 1 , i.e., m triangles sharing exactly one vertex. In this paper, we prove that R ( T n , F m ) = 2 n − 1 for n ≥ 3 m 2 − 2 m − 1 , and if T n = S n , then the range can be replaced by n ≥ max { m ( m − 1 ) + 1 , 6 ( m − 1 ) } , which is tight in some sense. [ABSTRACT FROM AUTHOR]