Spectral radius and homeomorphically irreducible spanning trees of graphs

2025/09/02 by Gao, Bingqian, Liu, Huiqing, Zhao, Jing
#05C35 #05C50 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2509.02021

Abstract

For a connected graph G, a spanning tree T of G is called a homeomorphically irreducible spanning tree (HIST) if T has no vertices of degree 2. Albertson \em et al. proved that it is NP-complete to decide whether a graph contains a HIST. In this paper, we provide some spectral conditions that guarantee the existence of a HIST in a connected graph. Furthermore, we also present some sufficient conditions in terms of the order of a graph G to ensure the existence of a HIST in G.

Citations

• 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
• Spectral radius of graphs forbidden C₇ or C₆^\triangle
• Spectral extrema of K_s,t-minor free graphs--On a conjecture of M. Tait
• Spectral extremal results with forbidding linear forests
• The spectral radius of graphs without paths and cycles of specified length
• Spectral radius and Hamiltonicity of graphs
• Bounds on graph eigenvalues II

Related

• On Homeomorphically Irreducible Spanning Trees in Cubic Graphs
• A neighborhood union condition for the existence of a spanning tree without degree 2 vertices
• Finding a HIST: Chordality, Structural Parameters, and Diameter
• Refinements of degree conditions for the existence of a spanning tree without small degree stems
• Spectral radius and spanning trees of graphs