The number of bounded‐degree spanning trees. Issue 3 (27th August 2022) - Yuster, Raphael
Abstract: For a graph G G , let c k ( G ) c_k(G) be the number of spanning trees of G G with maximum degree at most k k . For k ≥ 3 k3 , it is proved that every connected n n ‐vertex r r ‐regular graph G G with r ≥ n k + 1 rnk+1 satisfies c k ( G ) 1 / n ≥ ( 1 − o n ( 1 ) ) r · z k, c_k(G)^1/n(1-o_n(1))rz_k, where z k > 0 z_k>0 approaches 1 extremely fast (e.g., z 10 = 0 . 999971 z_10=0.999971 ). The minimum degree requirement is essentially tight as for every k ≥ 2 k2 there are connected n n ‐vertex r r ‐regular graphs G G with r = ⌊ n / ( k + 1 ) ⌋ − 2 r=n/(k+1)floor -2 for which c k ( G ) = 0 c_k(G)=0 . Regularity may be relaxed, replacing r r with the geometric mean of the degree sequence and replacing z k z_k with z k ∗ > 0 z_k^* >0 that also approaches 1, as long as the maximum degree is at most n ( 1 − ( 3 + o k ( 1 ) ) ln k / k ) n(1-(3+o_k(1))k/k) . The same holds with no restriction on the maximum degree as long as the minimum degree is at least n k ( 1 + o k ( 1 ) ) nk(1+o_k(1)) .