Bounds of the number of leaves of spanning trees in graphs without triangles

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


We prove that every connected graph with girth at least 4 and s vertices whose degree differs from 2 contains a spanning tree with atleast 1/3(s-2)+ 2 leaves. We describe series of examples showing that this bound is tight. This result, together with the bound for graphs with no restriction on the girth (in such a graph, one can construct a spanning tree with at least 1/4(s-2)+2 leaves) leads to the conjecture that for a graph with girth at least g, there exists a spanning tree at least g-2/2g-2(s-2)+ 2 leaves. We prove that this conjecture fails for g ≥ 10 and the bound cannot exceed 7/16s + 1/2. Bibliography: 14 titles.

Original languageEnglish (US)
Pages (from-to)557-563
Number of pages7
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 in graphs without triangles'. Together they form a unique fingerprint.

Cite this