Hamiltonicity of cubic 3-connected \(k\)-Halin graphs (Q1953458)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Hamiltonicity of cubic 3-connected \(k\)-Halin graphs |
scientific article |
Statements
Hamiltonicity of cubic 3-connected \(k\)-Halin graphs (English)
0 references
7 June 2013
0 references
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.
0 references
k-Halin graph
0 references
Hamiltonian cycles
0 references
k-edge Hamiltonian
0 references