2014/12/07 by Guantao Chen, Songling Shan, Chen, Guantao +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1412.2374
openalex publication_date 2014/12/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A spanning tree with no vertices of degree 2 is called a Homeomorphically irreducible spanning tree (HIST). Based on a HIST embedded in the plane, a Halin graph is formed by connecting the leaves of the tree into a cycle following the cyclic order determined by the embedding. Both of the determination problems of whether a graph contains a HIST or whether a graph contains a spanning Halin graph are shown to be NP-complete. It was conjectured by Albertson, Berman, Hutchinson, and Thomassen in 1990 that a \it every surface triangulation of at least four vertices contains a HIST (confirmed). And it was conjectured by Lovász and Plummer that \it every 4-connected plane triangulation contains a spanning Halin graph (disproved). Balancing the above two facts, in this paper, we consider generalized Halin graphs, a family of graph structures which are "stronger" than HISTs but "weaker" than Halin graphs in the sense of their construction constraints. To be exact, a generalized Halin graph is formed from a HIST by connecting its leaves into a cycle. Since a generalized Halin graph needs not to be planar, we investigate the minimum degree condition for a graph to contain it as a spanning subgraph. We show that there exists a positive integer n0 such that any 3-connected graph with n≥ n0 vertices and minimum degree at least (2n+3)/5 contains a spanning generalized Halin graph. As an application, the result implies that under the same condition, the graph G contains a wheel-minor of order at least n/2. The minimum degree condition in the result is best possible.