Premium
On homeomorphically irreducible spanning trees in cubic graphs
Author(s) -
HoffmannOstenhof Arthur,
Noguchi Kenta,
Ozeki Kenta
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22242
Subject(s) - mathematics , combinatorics , cubic graph , spanning tree , vertex (graph theory) , toroid , graph , plane (geometry) , line graph , geometry , voltage graph , physics , plasma , quantum mechanics
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. We also show several results on the existence of HISTs in plane and toroidal cubic graphs.