Generation of Non-Isomorphic Cubic Cayley Graphs

by Bijaya Rath

Abstract

This thesis investigates the generation of non-isomorphic simple cubic Cayley graphs. The research is motivated indirectly by the long standing conjecture that all Cayley graphs with at least three vertices are Hamiltonian. All simple cubic Cayley graphs of degree <= 7 were generated. By a simple Cayley graph is meant one for which the underlying Cayley digraph is symmetric and irreflexive. Put another way, each generator is an involution which is not the identity. Results are presented which show which pairs of non-conjugate triples of generators, up to degree 7, yield isomorphic Cayley graphs. These Cayley graphs range in size up to 5040, and include a number for which hamiltonicity or non-hamiltonicity has not been determined.

In addition to the census results some sufficient (but by no means necessary) conditions are shown for isomorphism between Cayley graphs, and an efficient method of counting non-conjugate triples of involutions is developed.

Index words: Cayley Graphs, Hamiltonian Graphs, Graph Isomorphism