Hamiltonicity of Cubic 3-Connected k-Halin Graphs

Abstract

We investigate here how far we can extend the notion of a Halin graph such that hamiltonicity is preserved. Let $H = T \cup C$ be a Halin graph, $T$ being a tree and $C$ the outer cycle. A $k$-Halin graph $G$ can be obtained from $H$ by adding edges while keeping planarity, joining vertices of $H - C$, such that $G - C$ has at most $k$ cycles. We prove that, in the class of cubic $3$-connected graphs, all $14$-Halin graphs are hamiltonian and all $7$-Halin graphs are $1$-edge hamiltonian. These results are best possible.