Graphs with homeomorphically irreducible spanning trees

Authors:

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.

This publication has 2 references indexed in Scilit: