Turán's problem and Ramsey numbers for trees

Zhi-Hong Sun; Lin-Lin Wang; Yi-Li Wu

paper

Turán's problem and Ramsey numbers for trees

arXiv:1110.2725

Abstract

Let $T_{n}^{1} = (V, E_{1})$ and $T_{n}^{2} = (V, E_{2})$ be the trees on $n$ vertices with $V = {v_{0}, v_{1}, \dots, v_{n - 1}}$ , $E_{1} = {v_{0} v_{1}, \dots, v_{0} v_{n - 3}, v_{n - 4} v_{n - 2}, v_{n - 3} v_{n - 1}}$ , and $E_{2} = {v_{0} v_{1}, \dots,$ $v_{0} v_{n - 3}, v_{n - 3} v_{n - 2}, v_{n - 3} v_{n - 1}}$ . In this paper, for $p \geq n \geq 5$ we obtain explicit formulas for $\ex(p;T_n^1)$ and $\ex(p;T_n^2)$, where $\ex(p;L)$ denotes the maximal number of edges in a graph of order $p$ not containing $L$ as a subgraph. Let $r(G\sb 1, G\sb 2)$ be the Ramsey number of the two graphs $G_{1}$ and $G_{2}$ . In this paper we also obtain some explicit formulas for $r (T_{m}, T_{n}^{i})$ , where $i \in {1, 2}$ and $T_{m}$ is a tree on $m$ vertices with $Δ (T_{m}) \leq m - 3$ .

21 pages

Cited by in corpus (1)

Turán's problem for trees $T_{n}$ with maximal degree $n - 4$