Cayley graphs: isomorphisms, automorphisms, Hamilton cycles and more

点击翻译按钮获取中文摘要

My proposed research will focus on Cayley graphs. In this context, graphs are models of networks, with "vertices" (points) representing nodes or terminals, and edges representing connections. Cayley graphs are graphs with nice symmetry properties: simple examples include the square, or the pentagram (star), which have rotational symmetry. These examples also have symmetries of reflection along various axes. Cayley graphs are interesting combinatorial objects to study for their own sakes, and they also provide a significant class of graphs for which powerful techniques of group theory (abstract algebra) can be brought to bear in exploring difficult problems that are of interest for all graphs. I plan to explore a number of different open problems on Cayley graphs, including: 1. finding algorithms to determine all of the symmetries of certain classes of Cayley graphs; 2. exploring graphs that can be represented as a Cayley graph in more than one way, as they show a variety of different symmetries; 3. proving structural theorems on highly symmetric graphs, using various modifications of a technique known as taking a quotient to reduce a graph to a smaller graph in the same family, characterising the irreducible graphs in the family and using this characterisation to prove structural theorems about all graphs in the family; and 4. finding Hamilton cycles in Cayley graphs: routes through the graph that visit every vertex precisely once.