Dirac's Condition for Spanning Halin Subgraphs

Source abstract

Let $G$ be an $n$-vertex graph with $n\ge 3$. A classic result of Dirac from 1952 asserts that $G$ is hamiltonian if $\delta(G)\ge n/2$. Dirac's theorem is one of the most influential results in the study of hamiltonicity and by now there are many related known results(see, e.g., [J. A. Bondy, Handbook of Combinatorics, Vol. 1, MIT Press, Cambridge, MA, 1995, pp. 3--110]. A Halin graph is a planar graph consisting of two edge-disjoint subgraphs: a spanning tree of at least four vertices and with no vertex of degree 2, and a cycle induced by the set of the leaves of the spanning tree. Halin graphs possess rich hamiltonicity properties such as being hamiltonian, hamiltonian connected, and almost pancyclic. As a continuous “generalization” of Dirac's theorem, in this paper, we show that there exists a positive integer $n_0$ such that any graph $G$ with $n\ge n_0$ vertices and $\delta(G)\ge (n+1)/2$ contains a spanning and pancyclic Halin subgraph $H$. In addition, for every nonhamiltonian cycle $C$ in $H$, there is a cycle $C'$ longer than $C$ such that $C'$ contains all vertices from $C$ and at most two more vertices not from $C$.