The number of spanning trees in graphs with a given degree sequence

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)269-274
Number of pages6
JournalRandom Structures & Algorithms
Volume6
Issue number2-3
DOIs
StatePublished - 1995
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • General Mathematics
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'The number of spanning trees in graphs with a given degree sequence'. Together they form a unique fingerprint.

Cite this