Forbidden Pairs and the Existence of a Spanning Halin Subgraph

A Halin graph is constructed from a plane embedding of a tree with no vertices of degree 2 by adding a cycle through its leaves in the natural order determined by the embedding. Halin graphs satisfy interesting properties. However, to our knowledge, there are no results giving a positive answer for “spanning Halin subgraph problem” (i.e., which graph has a Halin graph as a spanning subgraph) except for a conjecture by Lovász and Plummer which states that every 4-connected plane triangulation contains a spanning Halin subgraph. In this paper, we investigate the characterization of forbidden pairs guaranteeing the existence of a spanning Halin subgraph. In particular, we show that the set of such pairs is a very small class. Also, we show that { K_{1 , 3}, P₅} belongs to the set, but neither { K_{1 , 4}, P₅} nor { K_{1 , 3}, P₆} belongs to the set.