A new strategy for finding spanning trees without small degree stems

2023/03/07 by Michitaka Furuya, Furuya, Michitaka, Shoichi Tsuchiya +1 · 1 citation
Computer Science · #05C05 #05C07 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2303.03762

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

Abstract

For an integer k≥ 2, a spanning tree of a graph without vertices of degree from 2 to k is called a \it [2,k]-ST of the graph. The concept of [2,k]-STs is a natural extension of a homeomorphically irreducible spanning tree (or HIST), which is a well-studied graph structure. In this paper, we give a new strategy for finding [2,k]-STs. By using the strategy, we refine or extend a known degree-sum condition for the existence of a HIST. Furthermore, we also investigate a degree-product condition for the existence of a [2,k]-ST.

Cited by

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

Related

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