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 Books

Loading...

Similar Chapters

Loading...

Similar News

Loading...

Similar Articles

Loading...

Similar Article Headings

Loading...

مو لانا محمد سلمان خاں بھوپالی ندوی

مولانا محمد سلمان خاں بھوپالی ندوی مرحوم
ندوۃ العلما کے ایک اور لایق فرزند اور مولانا محمد عمران خاں بھوپالی ندوی مرحوم کے برادر خورد جناب مولانا محمد سلمان خاں ندوی مرحوم کی وفات حسرت آیات کی خبر بہت تاخیر سے ان کے صاحبزادے مولوی حافظ کلیم خاں ندوی کے ایک خط سے ملی، اناﷲ وانا الیہ راجعون۔ وہ دارالعلوم تاج المساجد کے سابق مہتمم تھے، لیکن ان کا سب سے روشن کارنامہ تاج المساجد کی تعمیر نو ہے۔ مولانا محمد عمران خاں ندوی مرحوم نے جس شاہانہ اولوالعزمی سے اس عظیم الشان مسجد کی تعمیر و تکمیل کا خاکہ بنایا تھا اس کو مولانا سلمان خاں صاحب نے حقیقتاً رنگ و روغن عطا کیا، جن لوگوں نے مسجد کی تعمیر و تکمیل میں ان کی شبانہ روز کی محنت، جانفشانی اور لگن دیکھی ہے وہ جانتے ہیں کہ اس تعمیر میں ان کا لہو تک شامل ہوگیا ایک عالم کی اس معمارانہ اور مہند سانہ مہارت پر بڑے بڑے انجینئر اور آرکی ٹیکٹ بھی حیران رہ گئے، طبعاً وہ نہایت شریف، متین، کم سخن اور مہمان نواز انسان تھے، اپنے تمام بیٹوں کو انھوں نے حفظ قرآن مجید کی دولت سے بہرہ یاب کیا اور سب کوند وہ ہیں تعلیم دلائی، وہ خود بڑے دیندار تھے متعدد بار حج بیت اﷲ کی سعادت حاصل کی۔ اﷲ تعالیٰ ان کی نیکیوں اور دینی خدمات کو قبول کرے اور جنت نعیم میں جگہ عطا فرمائے، آمین۔ ( عمیر الصدیق دریابادی ندوی ، اگست ۱۹۹۱ء)

 

غیر مسلموں کی تقریبات میں شرکت کی حدود وقیود: ایک تجزیاتی مطالعہ

This article aims to highlight an important aspect of Islamic Law, which relates to social life of a Muslim. Islamic law promotes social harmony and tolerance, but it makes it balance in the light of basic principles and objectives of Shar'īah. Likewise, Islamic law determines social relation between Muslims with each other as well as the relation of Muslims with Non-Muslim citizens in the Islamic state. Furthermore, it is very significant to know that a Muslim can participate in the traditional and religious functions of Non-Muslim or not? Islamic law has made some parameters in this regard, in this research paper we have focused on this specific issue of Islamic law and tried to explain the legal status of this issue in the light of Quran, Prophetic traditions, and opinions of Muslim Scholars. The research method applied in this paper is descriptive and critical study of different school of thoughts is also provided. Muslims have a long history of mutual contacts with the non-Muslims guided by the Shar’īah principles as they have come together in every age in different political and geographical contexts. In the early days of Islam, Muslims were in the minority. At that time, Muslims participated in the social life of their non-Muslims neighbors. Islam respects other religions. Provides all kinds of facilities to non-Muslims. And allows Muslims to participate in their legitimate programs.۔

Invigorating Inter-Domain Routing Using Software Defined Networking

Versatile applications over the Internet are producing unprecedented volume of data, flowing across the independently managed networking domains. Requirement of reliable communication, with better throughput and moderate latency, encourages Internet Service Providers to increase peering relationships with its immediate neighbors and beyond. Growing number of peering participants over emerging Internet Exchange Points (IXPs) highlights the significance of topological arrangement across the domains. IXPs are not only simplifying peering mesh of neighboring domains but also flattening the Internet topology from hierarchical structures over the course of time. Recent research works reveal the average edge multiplicity between IXPs more than four edges and entire range of IPv4 prefixes reachable through IXPs interconnection. Moreover, IXPs are adopting Software Define Networking (SDN) driven switching fabric, a trend that is becoming prominent with Toulouse, France and Tokyo, Japan Internet exchanges being clear case examples. In iii iv this thesis, we propose an architecture that interconnects SDN driven switching fabric of IXPs and exploit edge multiplicity between them to provision services across domains for the IXP peering participants. Traffic Engineering steered and policy compliant appropriate multiple paths are searched in a joint fashion to deploy at the IXPs switching fabric. We demonstrate that our proposal helps to achieve communication reliability across the domains with better network performance parameters like 54.60% increase in throughput.