Forbidden Pairs and the Existence of a Spanning Halin Subgraph

Guantao Chen; Jie Han; O. Suil; Songling Shan; Shoichi Tsuchiya

doi:10.1007/s00373-017-1847-7

Forbidden Pairs and the Existence of a Spanning Halin Subgraph

Guantao Chen, Jie Han, O. Suil, Songling Shan, Shoichi Tsuchiya^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

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 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.

Original language	English
Pages (from-to)	1321-1345
Number of pages	25
Journal	Graphs and Combinatorics
Volume	33
Issue number	5
DOIs	https://doi.org/10.1007/s00373-017-1847-7
Publication status	Published - 1 Sept 2017
Externally published	Yes

Keywords

Forbidden subgraph
Halin graph
Plane graph

Access to Document

10.1007/s00373-017-1847-7

Cite this

@article{8857174a6f9049c9a18a6be053191f9d,

title = "Forbidden Pairs and the Existence of a Spanning Halin Subgraph",

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 Lov{\'a}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 { K1 , 3, P5} belongs to the set, but neither { K1 , 4, P5} nor { K1 , 3, P6} belongs to the set.",

keywords = "Forbidden subgraph, Halin graph, Plane graph",

author = "Guantao Chen and Jie Han and O. Suil and Songling Shan and Shoichi Tsuchiya",

note = "Publisher Copyright: {\textcopyright} 2017, Springer Japan KK.",

year = "2017",

month = sep,

day = "1",

doi = "10.1007/s00373-017-1847-7",

language = "English",

volume = "33",

pages = "1321--1345",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "5",

}

TY - JOUR

T1 - Forbidden Pairs and the Existence of a Spanning Halin Subgraph

AU - Chen, Guantao

AU - Han, Jie

AU - Suil, O.

AU - Shan, Songling

AU - Tsuchiya, Shoichi

PY - 2017/9/1

Y1 - 2017/9/1

N2 - 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 { K1 , 3, P5} belongs to the set, but neither { K1 , 4, P5} nor { K1 , 3, P6} belongs to the set.

AB - 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 { K1 , 3, P5} belongs to the set, but neither { K1 , 4, P5} nor { K1 , 3, P6} belongs to the set.

KW - Forbidden subgraph

KW - Halin graph

KW - Plane graph

UR - http://www.scopus.com/inward/record.url?scp=85029171940&partnerID=8YFLogxK

U2 - 10.1007/s00373-017-1847-7

DO - 10.1007/s00373-017-1847-7

M3 - Article

AN - SCOPUS:85029171940

SN - 0911-0119

VL - 33

SP - 1321

EP - 1345

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 5

ER -

Forbidden Pairs and the Existence of a Spanning Halin Subgraph

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this