2022/07/29 by Raphael Yuster, Yuster, Raphael
Computer Science · Mathematics · #05C05 #05C30 #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2207.14574
openalex publication_date 2022/07/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a graph G, let ck(G) be the number of spanning trees of G with maximum degree at most k. For k ≥ 3, it is proved that every connected n-vertex r-regular graph G with r ≥ (n)/(k+1) satisfies ck(G)1/n ≥ (1-on(1)) r ⋅ zk where zk > 0 approaches 1 extremely fast (e.g. z10=0.999971). The minimum degree requirement is essentially tight as for every k ≥ 2 there are connected n-vertex r-regular graphs G with r=\lfloor n/(k+1) \rfloor -2 for which ck(G)=0. Regularity may be relaxed, replacing r with the geometric mean of the degree sequence and replacing zk with zk^* > 0 that also approaches 1, as long as the maximum degree is at most n(1-(3+ok(1))√(ln k/k)). The same holds with no restriction on the maximum degree as long as the minimum degree is at least (n)/(k)(1+ok(1)).