Hamiltonicity of covering graphs of trees

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