Ramsey numbers for trees

Zhi-Hong Sun

paper

Ramsey numbers for trees

arXiv:1103.2685

Abstract

For $n \geq 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}, \dots,$ $v_{n - 1}}$ and $E = {v_{0} v_{1}, \dots, 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 \geq 8$ we have $r (T_{n}^{'}, T_{n}^{*}) = r (T_{n}^{*}, T_{n}^{*}) = 2 n - 5$ , for $n > m \geq 7$ we have $r (K_{1, m - 1}, T_{n}^{*}) = m + n - 3$ or $m + n - 4$ according as $m - 1 ∣ (n - 3)$ or $m - 1 ∤ (n - 3)$ , for $m \geq 7$ and $n \geq (m - 3)^{2} + 2$ we have $r (T_{m}^{*}, T_{n}^{*}) = m + n - 3$ or $m + n - 4$ according as $m - 1 ∣ (n - 3)$ or $m - 1 ∤ (n - 3)$ .

10 pages