Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419304 | Discrete Applied Mathematics | 2015 | 8 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jennifer Diemunsch, Michitaka Furuya, Maryam Sharifzadeh, Shoichi Tsuchiya, David Wang, Jennifer Wise, Elyse Yeager,