Spanning Trees with Many Leaves in Graphs With Minimum Degree Three

Paul S. Bonsma

Research output: Contribution to journalArticleAcademicpeer-review

18 Citations (Scopus)

Abstract

We present two lower bounds for the maximum number of leaves over all spanning trees of a graph. For connected, triangle-free graphs on n vertices, with minimum degree at least three, we show that a spanning tree with at least $(n+4)/3$ leaves exists. For connected graphs with minimum degree at least three, without diamonds induced by vertices of degree three, we show that a spanning tree with at least $(2n+12)/7$ leaves exists. (A diamond is a $K_4$ minus one edge.) The proofs use the fact that spanning trees with many leaves correspond to small connected dominating sets. Both of these bounds are best possible for their respective graph classes. For both bounds, simple polynomial time algorithms that find spanning trees satisfying the bounds are given.
Original languageEnglish
JournalSIAM journal on discrete mathematics
Volume22
Issue number3
DOIs
Publication statusPublished - 2008
Externally publishedYes

Keywords

  • Spanning tree
  • Max Leaf
  • Connected Dominating Set
  • Extremal Graph Theory

Fingerprint Dive into the research topics of 'Spanning Trees with Many Leaves in Graphs With Minimum Degree Three'. Together they form a unique fingerprint.

Cite this