Hamiltonicity of cubic 3-connected \(k\)-Halin graphs (Q1953458)

Summary: 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.