An extremal theorem for non-isomorphic spanning trees

Zhifei Yan; Lu-Ming Zhang

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

An extremal theorem for non-isomorphic spanning trees

En palabras de los autores

Más de Combinatoria y matemática discreta ese día

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