✦ LIBER ✦

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

✍ Scribed by Seymour Schuster

Publisher: John Wiley and Sons
Year: 1983
Tongue: English
Weight: 224 KB
Volume: 7
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190070209

No coin nor oath required. For personal study only.

✦ Synopsis

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 Chartrand at the Fourth International Conference on Graph Theory and Applications held in Kalamazoo, 1980.

📜 SIMILAR VOLUMES

A lower bound on the number of spanning

A lower bound on the number of spanning trees with k end-vertices

✍ Katherine Heinrich; Guizhen Liu 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 286 KB 👁 1 views

If a graph G with cycle rank p contains both spanning trees with rn and with n end-vertices, rn < n, then G has at least 2p spanning trees with k end-vertices for each integer k, rn < k < n. Moreover, the lower bound of 2p is best possible. [ l ] and Schuster [4] independently proved that such span

On the number of spanning trees in direc

On the number of spanning trees in directed circulant graphs

✍ Zbigniew Lonc; Krzysztof Parol; Jacek M. Wojciechowski 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB

The independence number condition for th

The independence number condition for the existence of a spanning f-tree

✍ Hikoe Enomoto; Kenta Ozeki 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 123 KB 👁 1 views

## Abstract Let __G__ be a graph and __f__ be a mapping from __V__(__G__) to the positive integers. A subgraph __T__ of __G__ is called an __f__‐tree if __T__ forms a tree and __d__~__T__~(__x__)≤__f__(__x__) for any __x__∈__V__(__T__). We propose a conjecture on the existence of a spanning __f__‐t

On the asymptotic behavior of the maximu

On the asymptotic behavior of the maximum number of spanning trees in circulant graphs

✍ Lonc, Zbigniew; Parol, Krzysztof; Wojciechowski, Jacek M. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB 👁 3 views

The following asymptotic estimation of the maximum number of spanning trees f k (n) in 2kregular circulant graphs ( k ú 1) on n vertices is the main result of this paper: )) , where

The number of spanning trees in a class

The number of spanning trees in a class of double fixed-step loop networks

✍ Xuerong Yong; Yuanping Zhang; Mordecai J. Golin 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB

A Generalization of Szego's Theorem and

A Generalization of Szego's Theorem and the Power Theorem for Complex Interpolation

✍ Richard Rochberg 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 358 KB 👁 1 views