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图上探索一些不同的开放问题，包括： 1.找到算法来确定某些类别的凯莱图的所有对称性; 2.探索可以以多种方式表示为Cayley图的图，因为它们显示出各种不同的对称性; 3.证明高度对称图的结构定理，使用商技术的各种修改将图简化为同一族中的较小图，描述该族中的不可约图，并使用此描述来证明有关所有图的结构定理家族中;和 4.在凯莱图中寻找汉密尔顿圈：通过图的路线，访问每个顶点精确一次。