The Number of Spanning Trees in Graphs with Given Degree Sequence
The Number of Spanning Trees in Graphs with Given Degree Sequence
复制标题
DOI：
10.1002/rsa.3240060214
复制
发表时间：
1995-03
期刊：
影响因子：
--
通讯作者：
A. Kostochka
中科院分区：
文献类型：
--
作者：
A. Kostochka
本文对Alon [1]的思想作了改进，证明了对任意度序列为1<k = d1 <$d2 <$...<$dn的连通图G，G的生成树个数C（G）满足不等式. d（G）k−nO（log k/k）<$C（G）<$d（G）/（n - 1），.其中d（G）=（IIni=1 di）。对于n阶3-正则G，给出了C（G）的一个几乎精确下界. John Wiley & Sons，Inc.献给保罗·鄂尔多斯教授，在他80岁生日之际。
Alon's [1] idea is slightly refined to prove that for each connected graph G with degree sequence 1<k = d1≦d2≦…≦dn the number C(G) of spanning trees of G satisfies the inequality. d(G)k−nO(log k/k) ≦ C(G) ≦ d(G)/(n - 1),. where d(G) = (IIni=1 di). An almost exact lower bound for C(G) for 3-regular G on n vertices is also given. © 1994 John Wiley & Sons, Inc. Dedicated to Professor Paul Erdos on the occasion of his 80th birthday.