The number of bounded‐degree spanning trees. Issue 3 (27th August 2022)

• Record Type: Journal Article
• Authors: Yuster, Raphael
• Is Part Of: Random structures & algorithms. Volume 62:Issue 3(2023)
• Page Start: 737
• Page End: 757
• Publication Date: 2022-08-27
• Subjects: bounded degree -- counting -- spanning tree; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21118
• Languages: English
• ISSNs: 1042-9832

Abstract

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 $$ k\ge 3 $$, it is proved that every connected n $$ n $$ ‐vertex r $$ r $$ ‐regular graph G $$ G $$ with r ≥ n k + 1 $$ r\ge \frac{n}{k+1} $$ satisfies c k ( G ) 1 / n ≥ ( 1 − o n ( 1 ) ) r · z k, $$ {c}_k{(G)}^{1/n}\ge \left(1-{o}_n(1)\right)r\cdotp {z}_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 $$ k\ge 2 $$ there are connected n $$ n $$ ‐vertex r $$ r $$ ‐regular graphs G $$ G $$ with r = ⌊ n / ( k + 1 ) ⌋ − 2 $$ r=\left\lfloor n/\left(k+1\right)\right\rfloor -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^{\ast }>0 $$ that also approaches 1, as long as the maximum degree is at most n ( 1 − ( 3 + o k ( 1 ) ) ln k / k ) $$ n\left(1-\left(3+{o}_k(1)\right)\sqrt{\ln k/k}\right) $$ . 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 ) ) $$ \frac{n}{k}\left(1+{o}_k(1)\right) $$ .