𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Graphs with homeomorphically irreducible spanning trees

✍ Scribed by Michael O. Albertson; David M. Berman; Joan P. Hutchinson; Carsten Thomassen

Publisher
John Wiley and Sons
Year
1990
Tongue
English
Weight
509 KB
Volume
14
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 nearly present in all graphs of diameter 2. They do not necessarily occur in r‐regular or r‐connected graphs.

πŸ“œ SIMILAR VOLUMES

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

Spanning trees of dual graphs
Spanning trees of dual graphs
✍ Norman Biggs πŸ“‚ Article πŸ“… 1971 πŸ› Elsevier Science 🌐 English βš– 210 KB
A note on graphs with diameter-preservin
A note on graphs with diameter-preserving spanning trees
✍ Fred Buckley; Martin Lewinter πŸ“‚ Article πŸ“… 1988 πŸ› John Wiley and Sons 🌐 English βš– 182 KB πŸ‘ 1 views

The distance between a pair of vertices u, u in a graph G is the length of a shortest path joining u and u. The diameter diam(G) of G is the maximum distance between all pairs of vertices in G. A spanning tree Tof G is diameter preserving if diam(T) = diam(G). In this note, we characterize graphs th