论文标题
跨越树木的数量
The number of bounded-degree spanning trees
论文作者
论文摘要
对于图$ g $，让$ c_k（g）$是$ g $的跨越树木的数量，最多$ k $。对于$ k \ ge 3 $，可以证明，每个连接的$ n $ vertex $ r $ r $ - 带有$ r \ ge \ ge \ frac {n} {k+1} $满足$ c_k（g）^{g）^{1/n} \ ge（1-o_n（1-o_n（1-o_n（1-o_n（1-o_n（1-o_n（1-o_n（1-o_n（1- o_n（1-o_n（1-o_n（1-o_n））， $ z_ {10} = 0.999971 $）。最低学位要求基本上很紧张，因为对于每一个$ k \ ge 2 $都有连接的$ n $ vertex $ r $ - regular graphs $ g $，$ r = \ lfloor n/（k+1）\ rfloor -2 $，其中$ c_k（g）= 0 $。规律性可能会放松，用学位序列的几何平均值代替$ r $，并用$ z_k^*> 0 $代替$ z_k $，也接近$ 1 $，只要最高学位最多是$ n（1-（3+o_k（1））\ sqrt {\ sqrt {\ ln k/k/k/k/k}）$。只要最低度至少为$ \ frac {n} {k}（1+o_k（1））$，同样的情况也没有最大程度的限制。
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^* > 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))$.
