✦ LIBER ✦

Interpolation theorem for the number of pendant vertices of connected spanning subgraphs of equal size

✍ Scribed by C.A. Barefoot

Publisher: Elsevier Science
Year: 1984
Tongue: English
Weight: 162 KB
Volume: 49
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(84)90061-x

No coin nor oath required. For personal study only.

✦ Synopsis

At the 4th International Graph Theory Conference (1980), G. Chartrand posed the following problem: If a (connected) graph G contains spanning trees with m and n pendant vertices, respectively, with m < n, does G contain a spanning tree with k pendant vertices for every integer k, where m<k<n? Recently, S. Schuster showed that the answer is yes. Several variations of this interpolation theorem will be given including the following generalization: If a connected graph G contains connected spanning subgraphs of size r with m and n pendant vertices, respectively, with m < n, then G contains a connected spanning subgraph of size r with k pendant vertices for every integer k, where m < k < n.

📜 SIMILAR VOLUMES

Interpolation theorem for the number of

Interpolation theorem for the number of end-vertices of spanning trees

✍ Seymour Schuster 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 224 KB 👁 1 views

## Abstract 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