Forbidden Pairs and the Existence of a Spanning Halin Subgraph

Author(s)

Chen, Guantao ^{[1, 2]} ; Han, Jie ^[3] ; Suil, O. ^[4] ; Shan, Songling ^[5] ; Tsuchiya, Shoichi ^[6]

Affiliation

^[1] Georgia State Univ, Dept Math & Stat, Atlanta, GA 30303 - USA

^[2] Cent China Normal Univ, Fac Math & Stat, Wuhan, Hubei - Peoples R China

^[3] Univ Sao Paulo, Inst Matemat & Estat, Rua Matao 1010, BR-05508090 Sao Paulo - Brazil

^[4] SUNY, Dept Appl Math & Stat, Incheon 21985 - South Korea

^[5] Vanderbilt Univ, Dept Math, Nashville, TN 37240 - USA

^[6] Senshu Univ, Sch Network & Informat, Tama Ku, 2-1-1 Higashimita, Kawasaki, Kanagawa 2148580 - Japan

• Document type: Journal article
• Source: GRAPHS AND COMBINATORICS; v. 33, n. 5, p. 1321-1345, SEP 2017.
• Web of Science Citations: 1

Abstract

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 Lovasz 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 belongs to the set, but neither nor belongs to the set. (AU)

• FAPESP's process: 14/18641-5 - Hamilton cycles and tiling problems in hypergraphs
• Grantee: Jie Han
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• FAPESP's process: 15/07869-8 - Perfect matchings and Tilings in hypergraphs
• Grantee: Jie Han
• Support Opportunities: Scholarships abroad - Research Internship - Post-doctor