Spanning trees without adjacent vertices of degree 2

2018/01/22 by Lyngsie, Kasper Szabo, Merker, Martin
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1801.07025

Abstract

Albertson, Berman, Hutchinson, and Thomassen showed in 1990 that there exist highly connected graphs in which every spanning tree contains vertices of degree 2. Using a result of Alon and Wormald, we show that there exists a natural number d such that every graph of minimum degree at least d contains a spanning tree without adjacent vertices of degree 2. Moreover, we prove that every graph with minimum degree at least 3 has a spanning tree without three consecutive vertices of degree 2.

Related

• Refinements of degree conditions for the existence of a spanning tree without small degree stems
• On spanning trees with high internal degree
• Spanning trees with few branch vertices
• A neighborhood union condition for the existence of a spanning tree without samll degree vertices
• Spanning Trees in Graphs of High Minimum Degree with a Universal Vertex II: A Tight Result