Bounds of the number of leaves of spanning trees

A. V. Bankevich, D. V. Karpov

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


We prove that every connected graph with s vertices of degree not 2 has a spanning tree with at least 1/4(s- 2) + 2 leaves. Let G be a connected graph of girth g with υ vertices. Let maximal chain of successively adjacent vertices of degree 2 in the graph G does not exceed k ≥ 1. We prove that G has a spanning tree with at least αg,k(υ(G) - k - 2) + 2 leaves, where αg,k[g + 1/2]/[g + 1/2](k+3)+1 for k < g - 2; αg,k = g-2/(g-1)(k+2) for k ≥ g - 2. We present infinite series of examples showing that all these bounds are tight. Bibliography: 12 titles.

Original languageEnglish (US)
Pages (from-to)564-572
Number of pages9
JournalJournal of Mathematical Sciences (United States)
Issue number5
StatePublished - Aug 2012

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • General Mathematics
  • Applied Mathematics


Dive into the research topics of 'Bounds of the number of leaves of spanning trees'. Together they form a unique fingerprint.

Cite this