Abstract:We study the maximum number of spanning trees in connected $n$-vertex $C_4$-free graphs. For projective-plane orders $n=q^2+q+1$, we determine the spanning-tree count of every polarity graph and show that polarity graphs with exactly $q+1$ absolute points maximize this count within the polarity family, attaining $n^{(n-3)/2}$ spanning trees. Combined with a stability theorem of He, Ma and Yang \cite{HeMaYangCSIAM23}, this yields the same exact upper bound for all sufficiently dense $C_4$-free graphs in the known polarity stability regime. For arbitrary $C_4$-free graphs at these orders, we derive a global upper bound implying \[ \log \mathrm{st}(n,C_4)=\frac{n-3}{2}\log n+O(\sqrt n), \] where $\mathrm{st}(n,C_4)$ denotes the maximum number of spanning trees over connected $n$-vertex $C_4$-free graphs.
From: András London [view email]
[v1]
Wed, 25 Feb 2026 07:06:48 UTC (6 KB)
[v2]
Mon, 10 Aug 2026 09:31:27 UTC (8 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。