A Turán-type extremal problem for the number of spanning trees in $C_4$-free graphs
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\ge 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})\ge \frac12 q(q+1)^{2}$ for every prime power \(q\), and Füredi subsequently established the upper bound $\frac12 q(q+1)^{2}$ for $\ex(n,C_{4})$ whenever \(q\notin\{1, 7,9,11,13\}\). In this article, we prove that every \(C_{4}\)-free graph \(G\) on \(n\) vertices with at most \(\frac12 q(q+1)^{2}\) edges satisfies $τ(G)\le n^{(n-3)/2}$, where…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.34616
curl -X POST /api/v1/records/arxiv/2609.34616/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.34616/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'