Finding CCA groups and graphs algorithmically

Abstract

Given a group G, any subset C of G\{e} induces a Cayley graph, Cay(G,C). The set C also induces a natural edge-colouring of this graph. All affine automorphisms of the Cayley graph preserve this edge-colouring. A Cayley graph Cay(G,C) has the Cayley Colour Automorphism Property (is CCA), if all its colour-preserving automorphisms are affine. A group G is CCA if every connected Cayley graph on G is CCA. The goal of this thesis is to classify all groups of ‘small’ order to determine if they are CCA. In order to do this, we have developed two main algorithms that are the new contributions of this thesis. One algorithm finds all minimal generating sets for any group. The other algorithm uses this to test whether or not a group is CCA. These algorithms can also be used to determine whether or not a given Cayley graph is CCA.