Article ID Journal Published Year Pages File Type
419304 Discrete Applied Mathematics 2015 8 Pages PDF
Abstract

A spanning tree with no vertices of degree two is called a homeomorphically irreducible spanning tree (or a HIST  ) of a graph. In Furuya and Tsuchiya (2003), the sets of forbidden subgraphs that imply the existence of a HIST in a connected graph of sufficiently large order were characterized. In this paper, we focus on characterizing connected P5P5-free graphs which have a HIST. As applications of our main result, we also characterize forbidden pairs that imply the existence of a HIST.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , , , , ,