Forbidden Pairs and the Existence of a Spanning Halin Subgraph

Autor(es)

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

Afiliação do(s) autor(es)

^[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

• Tipo de documento: Artigo Científico
• Fonte: GRAPHS AND COMBINATORICS; v. 33, n. 5, p. 1321-1345, SEP 2017.
• Citações Web of Science: 1

Resumo

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)

• Processo FAPESP: 14/18641-5 - Circuitos hamiltonianos e problemas de ladrilhamento em hipergrafos
• Beneficiário: Jie Han
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 15/07869-8 - Emparelhamento perfeitos e ladrilhamentos em hipergrafos
• Beneficiário: Jie Han
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado