Hamiltonicity of Cubic 3-Connected k-Halin Graphs

  • Shabnam Malik
  • Ahmad Mahmood Qureshi
  • Tudor Zamfirescu
Keywords: Halin graph, k-Halin graph, Hamiltonian cycles, k-edge hamiltonian


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.
Article Number