Plane Triangulations Without a Spanning Halin Subgraph II
Guantao Chen, Hikoe Enomoto, Kenta Ozeki, Shoichi Tsuchiya · SIAM Journal on Discrete Mathematics · 2017
A Halin graph is a plane graph constructed from a planar drawing of a tree by connecting all leaves of the tree with a cycle which passes around the boundary of the graph. The tree must have four or more vertices and no vertices of degree two. Halin graphs have many nice properties such as being Hamiltonian and remaining Hamiltonian after any single vertex deletion. In 1975, Lovász and Plummer conjectured that every 4-connected plane triangulation contains a spanning Halin subgraph. We recently gave a negative answer to this conjecture. In this paper, we construct an infinite class of 5-connected plane triangulations without a spanning Halin subgraph. Our smallest example contains 512 vertices.