Turán's problem and Ramsey numbers for trees

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

¹ School of Mathematical Sciences Huaiyin Normal University Huaian, Jiangsu 223001, P.R. China
² School of Science China University of Mining and Technology Xuzhou, Jiangsu 221116, P.R. China

Colloquium Mathematicum, Tome 139 (2015) no. 2, pp. 273-298

Résumé

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,\ldots ,v_{n-1}\}$, $E_1=\{v_0v_1,\ldots ,v_0v_{n-3},v_{n-4}v_{n-2},v_{n-3}v_{n-1}\}$ and $E_2=\{v_0v_1,\ldots ,$ $v_0v_{n-3},v_{n-3}v_{n-2}, v_{n-3} v_{n-1}\}$. For $p\ge n\ge 5$ we obtain explicit formulas for ${\rm ex}(p;T_n^1)$ and ${\rm ex}(p;T_n^2)$, where ${\rm ex}(p;L)$ denotes the maximal number of edges in a graph of order $p$ not containing $L$ as a subgraph. Let $r(G_ 1, G_ 2)$ be the Ramsey number of the two graphs $G_1$ and $G_2$. 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 $\varDelta (T_m)\le m-3$.

Détail

DOI : 10.4064/cm139-2-8

Keywords: trees vertices ldots n ldots n n n n n ldots n n n n n obtain explicit formulas where denotes maximal number edges graph order containing subgraph ramsey number graphs obtain explicit formulas t where tree vertices vardelta m