Premium
Interpolation theorem for the number of end‐vertices of spanning trees
Author(s) -
Schuster Seymour
Publication year - 1983
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.3190070209
Subject(s) - combinatorics , spanning tree , mathematics , minimum degree spanning tree , wheel graph , minimum spanning tree , path graph , graph , discrete mathematics , graph power , line graph
The following interpolation theorem is proved: If a graph G contains spanning trees having exactly m and n end‐vertices, with m < n , then for every integer k, m < k < n, G contains a spanning tree having exactly k end‐vertices. This settles a problem posed by Chartrand at the Fourth International Conference on Graph Theory and Applications held in Kalamazoo, 1980.