Spanning-Tree Extremality in $C_4$-Free Graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.21639
curl -X POST /api/v1/records/arxiv/2602.21639/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.21639/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'