Bulletin of the Australian Mathematical Society

Research Article

RAMSEY NUMBERS FOR TREES

ZHI-HONG SUNa1

a1 School of Mathematical Sciences, Huaiyin Normal University, Huaian, Jiangsu 223001, PR China (email: zhihongsun@yahoo.com)

Abstract

For n≥5, let T n denote the unique tree on n vertices with Δ(T n )=n−2, and let T * n =(V,E) be the tree on n vertices with V ={v 0,v 1,…,v n−1} and E={v 0 v 1,…,v 0 v n−3,v n−3 v n−2,v n−2 v n−1}. In this paper, we evaluate the Ramsey numbers r(G m ,T n ) and r(G m ,T * n ) , where G m is a connected graph of order m. As examples, for n≥8 we have r(T n ,T * n )=r(T * n ,T * n )=2n−5 , for n>m≥7 we have r(K 1,m−1,T * n )=m+n−3 or m+n−4 according to whether m−1∣n−3 or m−1∤n−3 , and for m≥7 and n≥(m−3)2 +2 we have r(T * m ,T * n )=m+n−3 or m+n−4 according to whether m−1∣n−3 or m−1∤n−3 .

(Received September 24 2011)

2010 Mathematics subject classification

  • primary 05C35; secondary 05C05

Keywords and phrases

  • Ramsey number;
  • tree;
  • Turán’s problem

Footnotes

The author is supported by the National Natural Sciences Foundation of China (grant no. 10971078).