Skip to main content

Hamiltonicity of covering graphs of trees

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2023-12-12
Authors/Contributors
Abstract
In this thesis we investigate sufficient conditions for the Hamiltonicity of highly symmetric graphs. The subject of Hamiltonicity in such graphs, in particular, vertex-transitive graphs and specifically Cayley graphs has attracted significant attention from researchers over the years. The thesis focuses on a class of highly symmetric graphs known as regular coverings of graphs, or lifts of voltage graphs. We restrict our attention to lifts of voltage trees over cyclic groups. This class of graphs had been investigated for Hamiltonicity already by Batagelj and Pisanki in [11] and later by Hell et al. in [26]. Our results in Chapter 3 generalize the results in [11] and are independent of the results in [26]. Informally, we derive sufficient conditions for Hamiltonicity of covering graphs of trees based on special decompositions of such trees. In Chapter 4, we first derive two sufficient conditions for the existence of Hamiltonian cycle in covering graphs of trees over a cyclic group of large prime order. Then we use these conditions to prove a probabilistic result that given a tree T and a random voltage assignment on T with a fixed probability distribution, the limit of the probability that the covering graph over T is Hamiltonian for large enough cyclic group of prime order tends to 1 as the order of T tends to infinity. Finally, we prove that the covering graph of a tree T of a fixed maximum degree contains a cycle through almost all vertices provided the voltage assignment assigns elements to every loop of T that are coprime to the order of a large enough cyclic group. Most of the results of this thesis are included in the submitted manuscript [12].
Document
Extent
51 pages.
Identifier
etd22874
Copyright statement
Copyright is held by the author(s).
Permissions
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Supervisor or Senior Supervisor
Thesis advisor: Stacho, Ladislav
Language
English
Member of collection
Download file Size
etd22874.pdf 663.08 KB

Views & downloads - as of June 2023

Views: 31
Downloads: 1