𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Graphs with all spanning trees nonisomorphic

✍ Scribed by Lars Døvling Andersen; Preben Dahl Vestergaard

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
487 KB
Volume
155
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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 shown that any graph is an induced subgraph of a connected graph without two distinct, isomorphic spanning trees.

📜 SIMILAR VOLUMES

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

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