A neighborhood union condition for the existence of a spanning tree without samll degree vertices

2025/10/09 by Yibo Li, Li, Yibo, Fengming Dong +3
Computer Science · #Advanced Graph Theory Research #Interconnection Networks and Systems #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.2510.07655

Abstract

For an integer k≥2, a [2,k]-ST of a connected graph G is a spanning tree of G in which there are no vertices of degree between 2 and k. A [2,k]-ST is a natural extension of a homeomorphically irreducible spanning tree (HIST), which is a spanning tree without vertices of degree 2. In this paper, we give a neighborhood union condition for the existence of a [2,k]-ST in G. We generalize a known degree sum condition that guarantees the existence of a [2,k]-ST in G.

Citations

• A neighborhood union condition for the existence of a spanning tree without degree 2 vertices
• A new strategy for finding spanning trees without small degree stems
• Refinements of degree conditions for the existence of a spanning tree without small degree stems

Related

• A new strategy for finding spanning trees without small degree stems
• A neighborhood union condition for the existence of a spanning tree without degree 2 vertices
• Refinements of degree conditions for the existence of a spanning tree without small degree stems
• Spanning trees without adjacent vertices of degree 2
• On Homeomorphically Irreducible Spanning Trees in Cubic Graphs