𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Spanning trees of extended graphs

✍ Scribed by A. K. Kelmans

Publisher
Springer-Verlag
Year
1992
Tongue
English
Weight
364 KB
Volume
12
Category
Article
ISSN
0209-9683

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Spanning trees of dual graphs
Spanning trees of dual graphs
✍ Norman Biggs πŸ“‚ Article πŸ“… 1971 πŸ› Elsevier Science 🌐 English βš– 210 KB
Graphs with all spanning trees nonisomor
Graphs with all spanning trees nonisomorphic
✍ Lars DΓΈvling Andersen; Preben Dahl Vestergaard πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 487 KB

The paper presents some results on graphs that do not have two distinct isomorphic spanning trees. It is proved that any such connected graph with at least two vertices must have the property that each end-block has just one edge. On the other hand, the class of such graphs is quite large; it is sho

Graphs with homeomorphically irreducible
Graphs with homeomorphically irreducible spanning trees
✍ Michael O. Albertson; David M. Berman; Joan P. Hutchinson; Carsten Thomassen πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 509 KB

## Abstract It is an NP‐complete problem to decide whether a graph contains a spanning tree with no vertex of degree 2. We show that these homeomorphically irreducible spanning trees are contained in all graphs with minimum degree at least __c__√__n__ and in triangulations of the plane. They are ne

Maximizing spanning trees in almost comp
Maximizing spanning trees in almost complete graphs
✍ Gilbert, Bryan; Myrvold, Wendy πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 94 KB πŸ‘ 2 views

We examine the family of graphs whose complements are a union of paths and cycles and develop a very simple algebraic technique for comparing the number of spanning trees. With our algebra, we can obtain a simple proof of a result of Kel'mans that evening out path lengths increases the number of spa