The number of bounded-degree spanning trees

Abstract

For a graph $G$, let $c_k(G)$ be the number of spanning trees of $G$ with maximum degree at most $k$. For $k\ge 3$, it is proved that every connected $n$-vertex $r$-regular graph $G$ with $r\ge \frac{n}{k+1}$ satisfies $$c_k(G{)}^{1/n}\ge (1-o_n(1))r\cdot z_k$$ where $z_k>0$ approaches $1$ extremely fast (e.g. $z_{10}=0.999971$). The minimum degree requirement is essentially tight as for every $k\ge 2$ there are connected $n$-vertex $r$-regular graphs $G$ with $r=\lfloor n/(k+1)\rfloor -2$ for which $c_k(G)=0$. Regularity may be relaxed, replacing $r$ with the geometric mean of the degree sequence and replacing $z_k$ with $z_k^{\ast }>0$ that also approaches $1$, as long as the maximum degree is at most $n(1-(3+o_k(1))\sqrt{\ln k/k})$. The same holds with no restriction on the maximum degree as long as the minimum degree is at least $\frac{n}{k}(1+o_k(1))$.

25 pages, to appear in Random Structures & Algorithms