On Groups and Their Graphs

This thesis is an exploration of the relationship between groups and their Cayley graphs. Roughly speaking, a group is a set of objects with a rule of combination. Given any two elements of the group, the rule yields another group element, which depends on the two elements chosen. A familiar example of a group is the set of integers with addition as the combination rule. Addition illustrates some of the properties which a group combination rule must have, including that it is associative and that there is an element that, like 0, doesn\u27t change any element when combined with it. The information in a group can be represented by a graph, which is a collection of points, called vertices, and lines between them, called edges. In the case of the graph encoding a group, the vertices are elements of the group and the edges are determined by the combination rule. This graph is called a Cayley graph of the group. We discuss the basic correspondences between the structure of a group and the structure of its Cayley graphs, focusing particularly on the group properties which can be read off of some of its Cayley graphs. We then examine Cayley graphs in the context of the graph regular representation question, providing a review of graph regular representation results and some of the more salient strategies used to obtain them. Finally, we present new results about compatible colorings of Cayley graphs, which are proper colorings such that a particular subgroup of the automorphism group permutes the color classes. We prove that a minimal Cayley graph does not have a compatible coloring if and only if it is the Cayley graph of a cyclic group whose order is a product of distinct primes with a specific generating set