The number of spanning trees in regular graphs

Research output: Contribution to journalArticle

9 Scopus citations

Abstract

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
Volume1
Issue number2
DOIs
StatePublished - Jan 1 1990
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

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

  • Cite this