Extremal number of edges in graphs without homeomorphically irreducible spanning trees
classification
🧮 math.CO
keywords
extremalhistgraphmathrmoperatornamespanningbinomedges
read the original abstract
For integers $k\ge 1$ and $n\ge k+1$, let $\operatorname{ex}^{\mathrm{HIST}}_k(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 $\operatorname{ex}^{\mathrm{HIST}}_1(n)=\binom{n-2}{2}+2$ for $n\ge 9$, with $L_n$ as the unique extremal graph, and that $\operatorname{ex}^{\mathrm{HIST}}_2(n)=\binom{n-3}{2}+4$ for $n\ge 13$, with $B_n$ as the unique extremal graph. This provides a Tur\'an-type extremal result for spanning trees with no vertices of degree two.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.