The number of spanning trees in regular graphs

Research output: Contribution to journalArticlepeer-review

17 Scopus citations


Let C(G) denote the number of spanning trees of a graph G. It is shown that there is a function ϵ(k) that tends to zero as k tends to infinity such that for every connected, k‐regular simple graph G on n vertices C(G) = {k[1 − δ(G)]}n. where 0 ≤ δ(G) ≤ ϵ(k).

Original languageEnglish (US)
Pages (from-to)175-181
Number of pages7
JournalRandom Structures & Algorithms
Issue number2
StatePublished - 1990
Externally publishedYes

All Science Journal Classification (ASJC) codes

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


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

Cite this