Speaker: Hannah Hendrickson (UCF, Mathematics Dept)
Title: Embedding Cayley Graphs using Euler tours of other graphs
Abstract: We develop a method for determining whether certain kinds of Cayley map embeddings can exist by using multi-digraph representations (similar to Current graphs) of the data contained in the Cayley maps; "non-backtracking" Euler tours of these multi-digraphs correspond exactly to the permutations which define Cayley maps. We also classify all 3-regular graphs which admit such non-backtracking Euler tours. Finally, we show the essential equivalence of partitioning a group with n elements and the Cayley map embedding problem for complete graphs with n vertices. These three results together allow us to "instantly reject" potential Cayley maps for a given complete graph based on the properties of the underlying group itself, without having to manually verify the map's genus - thus greatly simplifying the process of directly computer-searching for Cayley map embeddings, by reducing it to a special case of the well-studied Subset Sum Problem.
Read More