In the master thesis we are dealing with a very well known family of graphs with a
lot of symmetry, namely with the so-called Cayley graphs. Regarding them there is an
interesting question about the existence of hamiltonian paths and hamiltonian cycles in
such graphs. Cayley graphs are graphs whose vertices are elements of a given group, while
the edges are given via a suitable generating set. A hamiltonian path of a graph is path
that visits all the vertices of a given graph, each exactly once. Similarly, a hamiltonian
cycle is a cycle that consists of all the vertices of a given graph.
The main topic of this thesis is the question about the existence of hamiltonian paths
between any two vertices in Cayley graphs of abelian groups. Graphs with this property
are said to be hamiltonian connected. In the process, we thoroughly study the results of
Chen and Quimpo from the article [6].
At the beginning we study the existence of hamiltonian paths in cartesian products
of two paths or of a cycle and a path. With the help of the obtained results we then
analyze the existence of hamiltonian paths between any two vertices in Cayley graphs of
abelian groups, since we can �nd such spanning subgraphs in these graphs. The results
are then generalized to Cayley graphs of abelian groups which are bipartite. The latter
are particularly interesting because they are not generally hamiltonian connected. Instead
of that they are hamiltonian laceable, where we only demand hamiltonian paths between
two vertices from di�erent parts of the bipartition. Finally, we present same well-known
graph families which are in fact Cayley graphs of abelian groups, and therefore we can
use the above theorem for their members. Additionally, we mention Johnson's graphs
and their hamiltonian connectedness. We also brie
y comment on the importance and
usefulness of the results from [6], which are mentioned by many authors in their articles
as a key step in their proofs.
|
