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

A Turán-type extremal problem for the number of spanning trees in C4-free graphs

  • Shaohan Xu
  • Fengming Dong
  • Kexiang Xu
Open at sourcePDFDOICite

Abstract

For a graph F, the Turán number ex(n,F) is the maximum number of edges in an F-free graph on n vertices. Let q≥ 2 be an integer and set n=q2+q+1. Brown and Erdős, Rényi and Sós independently proved that ex(n,C4)≥ 1/2 q(q+1)2 for every prime power q, and Füredi subsequently established the upper bound 1/2 q(q+1)2 for ex(n,C4) whenever q∉{1, 7,9,11,13}. In this article, we prove that every C4-free graph G on n vertices with at most 1/2 q(q+1)2 edges satisfies τ(G)≤ n(n−3)/2, where τ(G) denotes the number of spanning trees of G. In particular, for every prime power q∉{7,9,11,13}, the above upper bound on τ(G) is attained precisely by the orthogonal polarity graphs, thereby proving London's conjecture for all such q.

Related

  1. Turán-type extremal problems for unbalanced signed graphs
    Linfeng Xie, Keheng Zhu, Xiaogang Liu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Extremal Spanning Trees of Random Marked Graphs with Independent Edge Weights
    Ghurumuruhan Ganesan
    arXivPreprintCC BY 4.0Full textProbabilityarXiv
  3. Rooted spanning forests in wheel graphs: Fibonacci-Lucas formulas and extremal root configurations
    Shunya Tamura, Yuuho Tanaka
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Extremal Spanning Trees in Product Grid Graphs
    Jiechen Zhang
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsCombinatorics & discrete mathematicsarXiv
  5. A sharp upper bound on the number of spanning forests of regular graphs
    T. Wu, S. Lu, X. Dong
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{xu2026turántype,
  title = {{A Turán-type extremal problem for the number of spanning trees in $C_4$-free graphs}},
  author = {Shaohan Xu and Fengming Dong and Kexiang Xu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.34616},
  eprint = {2609.34616},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.34616},
}
RIS
TY  - UNPB
TI  - A Turán-type extremal problem for the number of spanning trees in C_4-free graphs
AU  - Shaohan Xu
AU  - Fengming Dong
AU  - Kexiang Xu
PY  - 2026
DA  - 2026/09/28
PB  - arXiv
DO  - 10.48550/arxiv.2609.34616
UR  - https://arxiv.org/abs/2609.34616
AB  - For a graph F, the Turán number ex(n,F) is the maximum number of edges in an F-free graph on n vertices. Let q≥ 2 be an integer and set n=q^2+q+1. Brown and Erdős, Rényi and Sós independently proved that ex(n,C_4)≥ 1/2 q(q+1)^2 for every prime power q, and Füredi subsequently established the upper bound 1/2 q(q+1)^2 for ex(n,C_4) whenever q∉{1, 7,9,11,13}. In this article, we prove that every C_4-free graph G on n vertices with at most 1/2 q(q+1)^2 edges satisfies τ(G)≤ n^(n−3)/2, where τ(G) denotes the number of spanning trees of G. In particular, for every prime power q∉{7,9,11,13}, the above upper bound on τ(G) is attained precisely by the orthogonal polarity graphs, thereby proving London's conjecture for all such q.
ER  -