An extremal theorem for non-isomorphic spanning trees

Zhifei Yan; Lu-Ming Zhang

In the authors' words

For a graph $G$ , let $τ_{i so} (G)$ denote the number of isomorphism classes of its spanning trees. For every fixed $d \geq 3$ and all sufficiently large $n$ , we prove that every connected $n$ -vertex graph $G$ with $δ (G) \geq d$ satisfies \[\tau_{iso}(G)\ge \tau_{iso}(K_{d,n-d})=A_dn^{d-1}+O_d(n^{d-2}),\] for an explicit constant $A_{d} > 0$ , and $K_{d, n - d}$ is the unique minimizer. This confirms a conjecture of Bitonti, Michel and Scott and extends it to every $d \geq 3$ . We also show that any such graph with $O (n^{d - 1})$ spanning-tree types has all but a bounded number of vertices with the same $d$ neighbours.

Main resultThe abstract does not state a limitation.

An extremal theorem for non-isomorphic spanning trees

In the authors' words

More on Combinatorics & discrete math that day

Thinning and sprinkling: from robust sampling to almost Hamiltonicity

Boolean threshold functions, neuron capacity, and memory retrieval

The Marcus-Minc Transform Inequality

The coarse Erd\H{o}s-P\'{o}sa theorem

A Combinatorial Proof of Hilton's Conjecture and Beyond