The topic of this MSc Thesis arises from the field of algebraic graph theory, where, among other things, we deal with graph symmetries. Symmetries, also called graph automorphisms, are permutations of vertices, which preserve adjacency. If there are automorphisms that ensure we can
map one vertex into any other one the graph is said to be vertex-transitive. Examples of vertextransitive graphs are Cayley graphs. Cayley graphs, and cubic Cayley graphs in particular, have been desireable research object over the last couple of decades due to their high degree of symmetry.
In the MSc Thesis we are interested in symmetries of members of a specific family of cubic graphs, called Honeycomb Toroidal Graphs (denoted by HTG). They are determined by three parameters - m, n and l and have mn vertices. After the preliminary presentation of the prerequisite theory we
first define Honeycomb Toroidal Graphs and present some of their basic structural properties. We show, among other things, that all HTG graphs are bipartite, vertex-transitive and are of girth at most 6. Some of them also possess cycles of length 4. We show that there are exactly three families
of HTG graphs of girth 4. Later on we provide the proof of each HTG graph being isomorphic to a Cayley graph on an appropriate generalized dihedral group with respect to the connection set of three involutions, thereby placing them in a well-known family of (vertex-transitive) graphs.
Moreover, the edges of such Cayley graphs can be naturally colored with three colors in a way that the three edges incident to any vertex are of distinct colors. Automorphisms which preserve or permute these colors are called “color” automorphisms. The Honeycomb Toroidal Graphs have received considerable attention over the last few decades not only by mathematicians but also by computer scientists. Until recently, the question of their symmetries hasn't been explored much. In a recent survey [1] Brian Alspach gathered most of the known results on HTG graphs and discussed a few research problems regarding them. In the MSc Thesis we focus on two of them, both of which concern symmetries of these graphs. Our main purpose is to determine the order of the automorphism group of each HTG graph in terms of all three parameters and to classify those with the smallest possible group of automorphisms. We divide the family of all HTG graphs roughly into two parts. The first part admits only color automorphisms while the second one admits automorphisms that are not color permuting. The main point of interest of the latter is that they are exceptional not only among HTG graphs but also among all cubic graphs. The origins of large automorphism groups of these graphs are examined more closely.
|
