期刊论文

Tsuchiya, Shoichi

英文

Graphs and Combinatorics

0911-0119

2017

33

5

1321-1345

10.1007/s00373-017-1847-7

FAPESPFundacao de Amparo a Pesquisa do Estado de Sao Paulo (FAPESP) [2014/18641-5, 2015/07869-8]; National Research Foundation of KoreaNational Research Foundation of Korea [NRF-2017R1D1A1B03031758]; JSPS KAKENHI GrantMinistry of Education, Culture, Sports, Science and Technology, Japan (MEXT)Japan Society for the Promotion of ScienceGrants-in-Aid for Scientific Research (KAKENHI) [JP16K17646]; Senshu University; Grants-in-Aid for Scientific ResearchMinistry of Education, Culture, Sports, Science and Technology, Japan (MEXT)Japan Society for the Promotion of ScienceGrants-in-Aid for Scientific Research (KAKENHI) [16K17646] Funding Source: KAKEN

本校为其他机构

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