Search or add a thesis

Advanced Search (Beta)
Home > Hamiltonian Properties of Generalized Halin Graphs

Hamiltonian Properties of Generalized Halin Graphs

Thesis Info

Access Option

External Link

Author

Qureshi, Ahmad Mahmood

Supervisor

Ioan Tomescu

Program

PhD

Institute

Government College University

City

Lahore

Province

Punjab

Country

Pakistan

Thesis Completing Year

2008

Thesis Completion Status

Completed

Subject

Mathemaics

Language

English

Link

http://prr.hec.gov.pk/jspui/handle/123456789/79

Added

2021-02-17 19:49:13

Modified

2024-03-24 20:25:49

ARI ID

1676726356891

Similar


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

Similar News

Loading...

Similar Articles

Loading...

Similar Article Headings

Loading...