Ramsey numbers for trees II

Zhi-Hong Sun

paper

Ramsey numbers for trees II

arXiv:1410.7637

Abstract

Let $r (G_{1}, G_{2})$ be the Ramsey number of the two graphs $G_{1}$ and $G_{2}$ . For $n_{1} \geq n_{2} \geq 1$ let $S (n_{1}, n_{2})$ be the double star given by $V (S (n_{1}, n_{2})) = {v_{0}, v_{1}, \dots, v_{n_{1}}, w_{0}, w_{1}, \dots, w_{n_{2}}}$ and $E (S (n_{1}, n_{2})) = {v_{0} v_{1}, \dots, v_{0} v_{n_{1}}, v_{0} w_{0}, w_{0} w_{1}, \dots, w_{0} w_{n_{2}}}$ . In this paper we determine $r (K_{1, m - 1},$ $S (n_{1}, n_{2}))$ under certain conditions. For $n \geq 6$ let $T_{n}^{3} = S (n - 5, 3)$ , $T_{n}^{^{''}} = (V, E_{2})$ and $T_{n}^{^{'''}} = (V, E_{3})$ , where $V = {v_{0}, v_{1}, \dots, v_{n - 1}}$ , $E_{2} = {v_{0} v_{1}, \dots, v_{0} v_{n - 4}, v_{1} v_{n - 3}, v_{1} v_{n - 2},$ $v_{2} v_{n - 1}}$ and $E_{3} = {v_{0} v_{1}, \dots, v_{0} v_{n - 4}, v_{1} v_{n - 3}, v_{2} v_{n - 2}, v_{3} v_{n - 1}}$ . We also obtain explicit formulas for $r$ $(K_{1, m - 1}, T_{n})$ , $r (T_{m}^{'}, T_{n})$ $(n \geq m + 3)$ , $r (T_{n}, T_{n})$ , $r (T_{n}^{'}, T_{n})$ and $r (P_{n}, T_{n})$ , where $T_{n} \in {T_{n}^{''}, T_{n}^{'''}, T_{n}^{3}}$ , $P_{n}$ is the path on $n$ vertices and $T_{n}^{'}$ is the unique tree with $n$ vertices and maximal degree $n - 2$ .

arXiv comment25 pages (published version)