Abstract
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(logk/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.
Original language | English (US) |
---|---|
Pages (from-to) | 269-274 |
Number of pages | 6 |
Journal | Random Structures & Algorithms |
Volume | 6 |
Issue number | 2-3 |
DOIs | |
State | Published - 1995 |
Externally published | Yes |
ASJC Scopus subject areas
- Software
- General Mathematics
- Computer Graphics and Computer-Aided Design
- Applied Mathematics