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