Cayley graphs: isomorphisms, automorphisms, Hamilton cycles and more

凯莱图：同构、自同构、汉密尔顿循环等

• 批准号: 238552-2011
• 负责人: Morris, Joy
• 金额: $ 0.73万
• 依托单位: University of Lethbridge
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=570443
• 关键词: Cayley; graphs; isomorphisms; automorphisms; Hamilton

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.

我提议的研究将集中在凯莱图上。 在这种情况下，图是网络模型，“顶点”（点）代表节点或终端，边代表连接。 凯莱图是具有良好对称性的图：简单的例子包括具有旋转对称性的正方形或五角星形（星形）。 这些例子还具有沿各个轴的反射对称性。 凯莱图本身就是值得研究的有趣组合对象，它们还提供了一类重要的图，可以利用群论（抽象代数）的强大技术来探索所有图都感兴趣的难题。 我计划探索凯莱图上的许多不同的开放问题，包括： 1. 寻找算法来确定某些凯莱图类别的所有对称性； 2. 探索可以用多种方式表示为凯莱图的图，因为它们表现出各种不同的对称性； 3. 证明高度对称图上的结构定理，使用称为取商的技术的各种修改将图简化为同一族中的较小图，表征该族中的不可约图并使用该表征来证明关于该族中所有图的结构定理；和 4. 在凯莱图中找到哈密尔顿循环：通过图中的路线，精确地访问每个顶点一次。