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

Asian Research Index Whatsapp Chanel
Asian Research Index Whatsapp Chanel

Join our Whatsapp Channel to get regular updates.

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

ذاتی مفادات اور عناد پر لڑائی جھگڑے

ذاتی عناد اور مفاد پر لڑائی جھگڑے

                ہمارے معاشرے کو آج پہلی ضرورت تو یکجہتی کی ہے۔ خود غرضی، قتل وغارت، لوٹ مار انتشار اور خلفشار کو ختم کرنے کے لیے انسانی یکجہتی کی ضرورت ہے اور اس کے لیے ہمیں اپنے مفاد اور دشمنی کو بھلا کرملک کا سوچنا ہو گا۔ذاتی عناد کی خاطر جب ہم دوسروں کی خوشیوں کو قربان کردیتے ہیں تو گویا ہم اس راستے پر چل نکلتے ہیںجو منزل سے محروم ہے ، کٹھن سفر مقدر بن جاتا ہے۔اس میں کوئی شک نہیں کہ اتحاد،ایمان ، اتفاق اور یکجہتی انسان کی سب سے بڑی طاقت ہے۔ایک کامیاب زندگی گزارنے کے لیے ہمیں اس کو اپنا شعار بنانا ہو گا۔ اس سے ہی تہذیب، وجود اور سماجی نظام نشوونما پاتے ہیں۔مگر اس حقیقت کو جانتے ہوئے بھی کہ اتحاد ہی ہمارا ترقی کی طرف پہلا قدم ہے ہم بدقسمتی سے ایسے معاشرے کا حصہ ہیں جہاں یکجہتی کا فقدان ہے۔خوشیوں سے محروم انسانوں کے مسائل سے قطع تعلقی کی وجہ سے یہ خامی جڑ پکڑتی جا رہی ہے۔

                دنیا کی تمام اقوام و مذاہب میں یہ شرف سب سے پہلے دین اسلام کو حاصل ہے جس نے یکجہتی کا درس دیا ہے۔بلا تفریق اسلام نیانسانی برادری اور مذہب وملت کا وہ نقشہ کھینچا ہے جس پر سچے دل سے عمل کیا جائے تو یہ ذاتی عناد اور مفاد پر لڑائی جھگڑے کرنے والی دنیا جنت کا منظر پیش کرنے لگے۔ ہمیں خود اس بات کا اعتراف کرنا ہے کہ ہم ہی دست  وبازو اور شریک کار ہیں جو انتشار کی وجہ بنے ہیں۔اس معاشرتی پس ماندگی کو ختم کرنا ہو گا اور اس کے لیے بھی ہمیں خود ہی کوشش کرنا ہو گی۔ اقتدار کے نام پر اور دوسروں  سے اختلاف کے چکر...

Awareness and Accessibility of Right to Information Act: A Comparative Study of Minorities within Pakistan and India

Right to Information (RTI) has become one of the major laws to strengthen the democracy of a country. Therefore, this study aims to analyze the awareness and accessibility of RTI for minorities in Pakistan and India. In this regard, a survey questionnaire was distributed to the total of 50 Pakistani Hindus and 50 Indian Muslims under snowball sampling method. The findings were analyzed with the help of independent-samples t-test on SPSS. Findings indicate Pakistani Hindus have only 12% awareness and right to access information as compare to Indian Muslims. For the future studies, there is a need to develop awareness of Right to Information specially in Pakistan in order to improve accountability and transparency in the structure of government.

Gene Identification in Mendelian Disorders Using Whole Exome Sequencing

Genetic disorders are a major cause of disabling conditions in regions of the world with high rates of consanguinity. Pakistan has a tradition of consanguineous marriages and therefore a high prevalence of Mendelian disorders. Charcot-Marie-Tooth syndrome and autosomal recessive spastic ataxia of Charlevoix-Saguenay affect peripheral nerves leading to severe foot deformity. Cerebral palsy, ataxia telangiectasia and hereditary multiple exostoses are some examples of the disorders that renders a person incapable of spending a normal life style. Such abnormalities may incapacitate the socioeconomic development of a country by putting forth major burden with respect to providing health care facilities. Importantly, ensuring the normality of a fetus will likely decrease the number of pregnancies a couple may have thereby decreasing the burden on society and family. Recent advancements in genomics enable genetic screening of large cohorts. Next generation sequencing technologies are used to identify genes, gene variants and variable expression associated with specific phenotypes. Exonic regions are known to contain most of the variants responsible for Mendelian disorders. Traditional approaches like linkage analysis and Sanger sequencing of candidate genes are costly or time consuming and a large samples size is required for this purpose. In this study ten inbred families from Pakistan were investigated using whole exome sequencing as a diagnostic and mutation identifying tool. Variants form whole exome sequencing were prioritized based on their functional relevance, disease association, pedigree information, inheritance pattern and pathogenicity scores using bioinformatics software. All the variants were validated through Sanger sequencing to rule out errors. Five novel mutations and two previously reported mutations were identified in this study. These variants were also evaluated for their functional impact using various bioinformatics tools. The findings in this study will help in understanding the disease mechanism and related pathways as well as annotating various entities of genome. The incidence of these disorders in Pakistan can be reduced through efficient carrier screening, genetic counseling, prenatal diagnosis and improved therapeutic approaches.