Extremal number of edges in graphs without homeomorphically irreducible spanning trees

Abstract

For integers $k\ge 1$ and $n\ge k+1$, let ${\mathrm{ex}}_k^{\mathrm{HIST}}(n)$ denote the maximum number of edges in a $k$-connected graph of order $n$ which contains no homeomorphically irreducible spanning tree (or briefly HIST). We determine these extremal numbers for $k=1$ and $k=2$. More precisely, we prove that ${\mathrm{ex}}_1^{\mathrm{HIST}}(n)=\left(\genfrac{}{}{0ex}{}{n-2}{2}\right)+2$ for $n\ge 9$, with $L_n$ as the unique extremal graph, and that ${\mathrm{ex}}_2^{\mathrm{HIST}}(n)=\left(\genfrac{}{}{0ex}{}{n-3}{2}\right)+4$ for $n\ge 13$, with $B_n$ as the unique extremal graph. This provides a Turán-type extremal result for spanning trees with no vertices of degree two.