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