Abstract:
A Halin graph is a graph H = T ∪ C, where T is a tree with no vertex of degree
two, and C is a cycle connecting the end-vertices of T in the cyclic order determined
by a plane embedding of T . Halin graphs were introduced by R. Halin [16] as a class
of minimally 3-connected planar graphs. They also possess interesting Hamiltonian
properties. They are 1-Hamiltonian, i.e., they are Hamiltonian and remain so after
the removal of any single vertex, as Bondy showed (see [23]). Moreover, Barefoot
proved that they are Hamiltonian connected, i.e., they admit a Hamiltonian path be-
tween every pair of vertices [1]. Bondy and Lov ́asz [6] and, independently, Skowronska
[33] proved that Halin graphs on n vertices are almost pancyclic, more precisely they
contain cycles of all lengths l (3 ≤ l ≤ n) except possibly for a single even length.
Also, they showed that Halin graphs on n vertices whose vertices of degree 3 are all on
the outer cycle C are pancyclic, i.e., they must contain cycles of all lengths from 3 to n.
In this thesis, we define classes of generalized Halin graphs, called k-Halin graphs,
and investigate their Hamiltonian properties.
In chapter 4, we define k-Halin graph in the following way.
A 2-connected planar graph G without vertices of degree 2, possessing a cycle C
such that
(i) all vertices of C have degree 3 in G, and
(ii) G − C is connected and has at most k cycles
is called a k-Halin graph.
A 0-Halin graph, thus, is a usual Halin graph. Moreover, the class of k-Halin
graphs is contained in the class of (k + 1)-Halin graphs (k ≥ 0).
We shall see that, the Hamiltonicity of k-Halin graphs steadily decreases as k
increases. Indeed, a 1-Halin graph is still Hamiltonian, but not Hamiltonian con-
nected, a 2-Halin graph is not necessarily Hamiltonian but still traceable, while a
3-Halin graph is not even necessarily traceable. The property of being 1-Hamiltonian,
Hamiltonian connected or almost pancyclic is not preserved, even by 1-Halin graphs.
However, Bondy and Lov ́asz’ result about the pancyclicity of Halin graphs with no
inner vertex of degree 3 remains true even for 3-Halin graphs.
The property of being Hamiltonian persists, however, for large values of k in
cubic 3-connected k-Halin graphs. In chapter 5, it will be shown that every cubic 3-
connected 14-Halin graph is Hamiltonian. A variant of the famous example of Tutte
[37] from 1946 which first demonstrated that cubic 3-connected planar graphs may not
be Hamiltonian, is a 21-Halin graphs. The cubic 3-connected planar non-Hamiltonian
graph of Lederberg [21], Bos ́ak [7] and Barnette, which has smallest order, is 53-Halin.
The sharpness of our result is proved by showing that there exist non-Hamiltonian
cubic 3-connected 15-Halin graphs.