Turán's Problem for Trees

Abstract

For a forbidden graph $L$, let $ex(p;L)$ denote the maximal number of edges in a simple graph of order $p$ not containing $L$. Let $T_n$ denote the unique tree on $n$ vertices with maximal degree $n-2$, and let $T_n^{\ast }=(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 the paper we give exact values of $ex(p;T_n)$ and $ex(p;T_n^{\ast })$.

19 pages