{"id":"arxiv/2609.34616","url":"https://arxiv.org/abs/2609.34616","tags":["math.CO"],"score":0,"title":"A Turán-type extremal problem for the number of spanning trees in $C_4$-free graphs","domain":"math.CO","source":"arxiv","authors":["Shaohan Xu","Fengming Dong","Kexiang Xu"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-28","reactions":{}}