|
|||||
|
|
Graphs with homeomorphically irreducible spanning trees |
|
| Authors: | Michael O Albertson David M Berman Joan P Hutchinson Carsten Thomassen |
| 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. |
| Keywords: | |