Spanning trees with many leaves

Guoli Ding; Thor Johnson; Paul Seymour

doi:10.1002/jgt.1013

Spanning trees with many leaves

Guoli Ding, Thor Johnson, Paul Seymour

Mathematics

Research output: Contribution to journal › Article › peer-review

45 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 language	English (US)
Pages (from-to)	189-197
Number of pages	9
Journal	Journal of Graph Theory
Volume	37
Issue number	4
DOIs	https://doi.org/10.1002/jgt.1013
State	Published - Aug 2001

All Science Journal Classification (ASJC) codes

Geometry and Topology

Keywords

Leaves
Tree

Access to Document

10.1002/jgt.1013

Cite this

@article{9e993bf7eaa24c9ebf29dfe0a372dc69,

title = "Spanning trees with many leaves",

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.",

keywords = "Leaves, Tree",

author = "Guoli Ding and Thor Johnson and Paul Seymour",

year = "2001",

month = aug,

doi = "10.1002/jgt.1013",

language = "English (US)",

volume = "37",

pages = "189--197",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "4",

}

TY - JOUR

T1 - Spanning trees with many leaves

AU - Ding, Guoli

AU - Johnson, Thor

AU - Seymour, Paul

PY - 2001/8

Y1 - 2001/8

N2 - 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.

AB - 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.

KW - Leaves

KW - Tree

UR - http://www.scopus.com/inward/record.url?scp=33751313593&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33751313593&partnerID=8YFLogxK

U2 - 10.1002/jgt.1013

DO - 10.1002/jgt.1013

M3 - Article

AN - SCOPUS:33751313593

SN - 0364-9024

VL - 37

SP - 189

EP - 197

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 4

ER -

Spanning trees with many leaves

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this