On Homeomorphically Irreducible Spanning Trees in Cubic Graphs

2015/07/28 by Hoffmann-Ostenhof, Arthur, Noguchi, Kenta, Ozeki, Kenta · 1 citation
#05Cxx #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1507.07689

Abstract

A spanning tree without a vertex of degree two is called a Hist which is an abbreviation for homeomorphically irreducible spanning tree. We provide a necessary condition for the existence of a Hist in a cubic graph. As one consequence, we answer affirmatively an open question on Hists by Albertson, Berman, Hutchinson and Thomassen.

Cited by

• Finding a HIST: Chordality, Structural Parameters, and Diameter

Related

• Spectral radius and homeomorphically irreducible spanning trees of graphs
• 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
• Special Hist-Snarks
• Finding a HIST: Chordality, Structural Parameters, and Diameter