𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Katherine Heinrich; Guizhen Liu

Publisher
John Wiley and Sons
Year
1988
Tongue
English
Weight
286 KB
Volume
12
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 spanning trees always existed. Their methods, however, were different. Recently, Lin [3] gave a new proof of the above result.

The purpose of this paper is to show that, if G contains both spanning trees with m and with n end-vertices m < n, then G contains at least 2p spanning trees with k end-vertices for every integer k, m < k < a, where p is the cycle rank of G. An example will be given to show that this result is best possible.

πŸ“œ 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

A lower bound on the independence number
A lower bound on the independence number of arbitrary hypergraphs
✍ Thiele, Torsten πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 104 KB πŸ‘ 3 views

We present a lower bound on the independence number of arbitrary hypergraphs in terms of the degree vectors. The degree vector of a vertex v is given by d is the number of edges of size m containing v. We define a function f with the property that any hypergraph H = (V, E) satisfies Ξ±(H) β‰₯ v∈V f (d