𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Topological complexity of graphs and their spanning trees

✍ Scribed by R. Nahum; S. Zafrany

Book ID
105332564
Publisher
Akadmiai Kiad
Year
1995
Tongue
English
Weight
592 KB
Volume
66
Category
Article
ISSN
1588-2632

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Spanning trees of extended graphs
Spanning trees of extended graphs
✍ A. K. Kelmans πŸ“‚ Article πŸ“… 1992 πŸ› Springer-Verlag 🌐 English βš– 364 KB
Spanning trees of dual graphs
Spanning trees of dual graphs
✍ Norman Biggs πŸ“‚ Article πŸ“… 1971 πŸ› Elsevier Science 🌐 English βš– 210 KB
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