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.

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