Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 43 min ago
PreprintarXiv licencearXiv

An extremal theorem for non-isomorphic spanning trees

  • Zhifei Yan
  • Lu-Ming Zhang
Open at sourcePDFDOICite

Abstract

For a graph G, let τiso(G) denote the number of isomorphism classes of its spanning trees. For every fixed d≥3 and all sufficiently large n, we prove that every connected n-vertex graph G with δ(G)≥ d satisfies τiso(G)≥ τiso(Kd,n−d)=Adnd−1+Od(nd−2), for an explicit constant Ad>0, and Kd,n−d is the unique minimizer. This confirms a conjecture of Bitonti, Michel and Scott and extends it to every d≥3. We also show that any such graph with O(nd−1) spanning-tree types has all but a bounded number of vertices with the same d neighbours.

Related

  1. Extremal Spanning Trees of Random Marked Graphs with Independent Edge Weights
    Ghurumuruhan Ganesan
    arXivPreprintCC BY 4.0Full textProbabilityarXiv
  2. A Turán-type extremal problem for the number of spanning trees in C4-free graphs
    Shaohan Xu, Fengming Dong, Kexiang Xu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Extremal Spanning Trees in Product Grid Graphs
    Jiechen Zhang
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsCombinatorics & discrete mathematicsarXiv
  4. Spanning k-trees and the colorful Carathéodory theorem
    Mikhail Bludov, Alexander Polyanskii
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Spectral radius and edge-disjoint spanning trees of graphs with edge connectivity
    Jia Wei, Muhuo Liu, Zhifu You +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{yan2026extremal,
  title = {{An extremal theorem for non-isomorphic spanning trees}},
  author = {Zhifei Yan and Lu-Ming Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.30201},
  eprint = {2609.30201},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.30201},
}
RIS
TY  - UNPB
TI  - An extremal theorem for non-isomorphic spanning trees
AU  - Zhifei Yan
AU  - Lu-Ming Zhang
PY  - 2026
DA  - 2026/09/24
PB  - arXiv
DO  - 10.48550/arxiv.2609.30201
UR  - https://arxiv.org/abs/2609.30201
AB  - For a graph G, let τ_iso(G) denote the number of isomorphism classes of its spanning trees. For every fixed d≥3 and all sufficiently large n, we prove that every connected n-vertex graph G with δ(G)≥ d satisfies τ_iso(G)≥ τ_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≥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.
ER  -