The topic of the master's thesis comes from algebraic graph theory, where, among other things, we study graph symmetries and explore the possibilities to use them for solving problems related to graphs. Symmetry (or graph automorphism) is a concept we use to define some graph properties, for example vertex-transitivity. In such graphs we require that for every pair of vertices there is automorphism, which maps the first vertex into the second one. One of the reasons why this family of graphs is so interesting is because we can find various open questions about these graphs that attracts interest of numerous researchers. One of these questions is definitely the question of the existence of Hamiltonian cycles and paths in vertex-transitive graphs which has a long history and represents the main topic of this master's thesis.
The cycle of a given graph Γ is called a Hamiltonian cycle if it includes all vertices of the graph Γ (the Hamiltonian path is defined analogously). We still do not know of a single example of a finite connected vertex-transitive graph without a Hamiltonian path and we know of exactly five such graphs that do not have a Hamiltonian cycle (the Petersen graph, the Coxeter graph, their truncated graphs, and the path on two vertices). The main purpose of this master’s thesis is to give a broader insight into the problem of existence of Hamiltonian cycles and paths in vertex-transitive graphs. We primarily focus on different approaches to solving the given problem, and we also present an interesting idea of our own, which could prove useful in this field.
In the first part of the master’s thesis we present the family of vertex-transitive graphs in more detail. We then explore the possibilities of applying the concept of blocks of imprimitivity to the problem of existence of Hamiltonian cycles and paths in vertex-transitive graphs. Here we make an analysis of the existence of systems of blocks of imprimitivity for small cubic vertex-transitive graphs and then examine structural properties of subgraphs, induced on individual blocks of imprimitivity. We also consider the possibilities of lifting Hamiltonian cycles and paths from the quotient graphs corresponding to a suitable system of blocks of imprimitivity. In the next part of the master's thesis we investigate the role of semiregular automorphisms in the problem of existence of Hamiltonian cycles and paths in graphs. We are interested in the existence of semiregular automorphisms in vertex-transitive graphs and their properties, but we mainly focus on lifting Hamiltonian cycles from quotient graphs with respect to the set of orbits of the semiregular automorphism group. The last part of the master's thesis is dedicated to the study of Lazslo Babai's important result about the length of the longest cycles in vertex-transitive graphs. We also present an interesting idea, which has not yet been explored in the context of the hamiltonicity problem for vertex-transitive graphs.
|
