Hamiltonicity of Cubic 3-Connected k-Halin Graphs

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

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2013-03, Vol.20 (1)
Main Authors: Malik, Shabnam, Qureshi, Ahmad Mahmood, Zamfirescu, Tudor
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
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.
ISSN:1077-8926
1077-8926
DOI:10.37236/3188