Spanning trees with many leaves

Guoli Ding, Thor Johnson, Paul Seymour

Research output: Contribution to journalArticlepeer-review

37 Scopus citations

Abstract

We show that if G is a simple connected graph with |E(G)|≥|V(G)|+1/2t(t-1) and |V(G)|≠t+2, then G has a spanning tree with >t leaves, and this is best possible.

Original languageEnglish (US)
Pages (from-to)189-197
Number of pages9
JournalJournal of Graph Theory
Volume37
Issue number4
DOIs
StatePublished - Aug 2001

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • Leaves
  • Tree

Fingerprint Dive into the research topics of 'Spanning trees with many leaves'. Together they form a unique fingerprint.

Cite this