Refinements of degree conditions for the existence of a spanning tree without small degree stems

2023/03/04 by Michitaka Furuya, Akira Saito, Furuya, Michitaka +3 · 2 citations
Computer Science · Engineering · #05C05 #05C07 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #VLSI and FPGA Design Techniques

paper · pdf · doi:10.48550/arxiv.2303.02372

openalex publication_date 2023/03/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A spanning tree of a graph without no vertices of degree 2 is called a \it homeomorphically irreducible spanning tree (or a \it HIST) of the graph. Albertson, Berman, Hutchinson and Thomassen~[J. Graph Theory \bf 14 (1990), 247--258] gave a minimum degree condition for the existence of a HIST, and recently, Ito and Tsuchiya~[J. Graph Theory \bf 99 (2022), 162--170] found a sharp degree-sum condition for the existence of a HIST. In this paper, we refine these results, and extend the first one to a spanning tree in which no vertex other than the endvertices has small degree.

Cited by

• A neighborhood union condition for the existence of a spanning tree without samll degree vertices
• Spectral radius and homeomorphically irreducible spanning trees of graphs

Related

• 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
• A neighborhood union condition for the existence of a spanning tree without samll degree vertices
• On Homeomorphically Irreducible Spanning Trees in Cubic Graphs
• Spanning trees without adjacent vertices of degree 2