pith. sign in

arxiv: 2606.12093 · v1 · pith:SW3F75HAnew · submitted 2026-06-10 · 🧮 math.CO

Extremal number of edges in graphs without homeomorphically irreducible spanning trees

classification 🧮 math.CO
keywords extremalhistgraphmathrmoperatornamespanningbinomedges
0
0 comments X
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.