Premium
Spanning trees with many leaves
Author(s) -
Ding Guoli,
Johnson Thor,
Seymour Paul
Publication year - 2001
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.1013
Subject(s) - spanning tree , combinatorics , mathematics , minimum degree spanning tree , graph , minimum spanning tree , simple (philosophy) , simple graph , tree (set theory) , connectivity , discrete mathematics , philosophy , epistemology
We show that if G is a simple connected graph with$$|E\;({\bf G})|\geq |V\;(\,G)|+{1 \over 2}t\,\;(t-1)$$ and $|V(G)| \,\neq\,t+2$ , then G has a spanning tree with > t leaves, and this is best possible. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 189–197, 2001
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom