Graphs with homeomorphically irreducible spanning trees
Authors:
- 1 June 1990
- journal article
- Published by Wiley in Journal of Graph Theory
- Vol. 14 (2) , 247-258
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
This publication has 2 references indexed in Scilit:
- SPANNING TREES IN POLYTOPAL GRAPHSAnnals of the New York Academy of Sciences, 1979
- The number of homeomorphically irreducible trees, and other speciesActa Mathematica, 1959