Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.21639 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910032751230976 |
|---|---|
| author | London, András |
| author_facet | London, András |
| contents | We introduce a ``Kirchhoff--Turán'' variant of the extremal $C_4$ problem: among all simple connected $n$-vertex $C_4$-free graphs $G$, maximize the number of spanning trees $τ(G)$. For the projective-plane orders $n=q^2+q+1$ we compute an exact formula for the Erdős--Rényi orthogonal polarity graph $ER_q$, namely $τ(ER_q)=n^{(n-3)/2}$, via a polarity spectral identity and Kirchhoff's matrix--tree theorem. We also give an explicit general upper bound on $\mathrm{st}(n,C_4)$ at these $n$ using a sharp degree-sequence inequality for $τ(G)$ and a degree-balancing argument; this matches the lower bound in the leading exponential term. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_21639 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Maximum Number of Spanning Trees in $C_4$-Free Graphs London, András Combinatorics 05C30, 05C35, 05C50 We introduce a ``Kirchhoff--Turán'' variant of the extremal $C_4$ problem: among all simple connected $n$-vertex $C_4$-free graphs $G$, maximize the number of spanning trees $τ(G)$. For the projective-plane orders $n=q^2+q+1$ we compute an exact formula for the Erdős--Rényi orthogonal polarity graph $ER_q$, namely $τ(ER_q)=n^{(n-3)/2}$, via a polarity spectral identity and Kirchhoff's matrix--tree theorem. We also give an explicit general upper bound on $\mathrm{st}(n,C_4)$ at these $n$ using a sharp degree-sequence inequality for $τ(G)$ and a degree-balancing argument; this matches the lower bound in the leading exponential term. |
| title | On the Maximum Number of Spanning Trees in $C_4$-Free Graphs |
| topic | Combinatorics 05C30, 05C35, 05C50 |
| url | https://arxiv.org/abs/2602.21639 |