双Cayley图对称性理论与应用研究

Symmetry of graph is one of the important research topics in the algebraic graph theory. Increasingly, symmetrical graphs are being used in a wide range of applications，such as, the design of interconnection networks for large interacting arrays of processors in parallel computations, the group-based cryptography, the graph isomorphism problem (of relevence to computer science and to chemical documentation) and so on...This project proposes to study one important class of symmetrical graphs, namely, bi-Cayley graphs. A graph is said to be a bi-Cayley graph if it has a semiregular automorphism with two orbits on its vertex set. Increasingly, bi-Cayley graphs are being used in various classical fields of graph theory, such as the spectrum of graphs, the connectivity of graphs, n-extendable graphs, Hamitonial graphs, strongly regular graphs, highly symmetrical graphs, ect.. The purpose of this project is to consider the following topics regarding bi-Cayley graphs: Develop a theory of normality of bi-Cayley graphs; study bi-graph regular representations of finite groups; develop a theory of normal edge-transitive bi-Cayley graphs; study the 3-edge-colorable 3-valent bi-Cayley graphs. It aims to solve fundamental problems regarding bi-Cayley graphs, and to make significant and breaking progress and to develop useful theory for symmetry of graphs.

图的对称性是代数图论的核心内容之一。图的对称性在并行计算中处理器的大型相互作用阵列的通信网络的设计、基于群论的密码学、与计算机科学和化学文档相关的图的同构问题等许多领域有着越来越多的应用。.本项目计划研究一类重要的高对称性图, 即双Cayley图。若一个图有一个半正则自同构群且在其顶点集合上具有两个轨道,则称该图为双Cayley图。近年来，双Cayley图在越来越多的经典图论领域中找到了应用：从图的谱到图的连通性、从图的可扩性到图的Hamilton性、从强正则图到强对称图等等。本项目将致力于以下方面的研究：进一步发展双Cayley图的正规性理论；研究有限群的双图正则表示；发展一套研究正规边传递双Cayley图的理论；研究三度双Cayley图的三边可染色性等等。其目的是解决这些课题中的一些重大问题，在每个课题上取得突破性进展，发展一些图的对称性方面有用的理论。

图的对称性是代数图论的核心内容之一。图的对称性在并行计算中处理器的大型相互作用阵列的通信网络的设计、基于群论的密码学、与计算机科学和化学文档相关的图的同构问题等许多领域有着越来越多的应用。. 本项目首先系统研究了循环群、二面体群、亚循环群等重要群类上的双Cayley图的正规性，并将所得结果应用于构造具有特定对称性质的图类，如半对称图、半弧传递图、点传递非Cayley图等等，解决了Marusic-Sparl弱亚循环图问题、Marusic-Potocnik半对称四循环图问题、Li-双正规Cayley图问题等群与图领域重点公开问题。.本项目的另一代表性成果是系统研究了亚循环图与弱亚循环图，该项研究表明亚循环图一定是可裂弱亚循环图，但反之则不然。称可裂弱亚循环的非亚循环图为伪亚循环图。本项目刻画了存在n阶伪亚循环图的所有正整数n, 首次发现了伪亚循环图的三个无限类，提出了绝对可裂亚循环群、弱绝对可裂亚循环置换群等群论概念，解决了有关Aspach-Parson亚循环图、Li-Song-Wang亚循环Cayley图等公开问题。. 本项目还研究了Cayley图的正规性、k-齐性图、图的直积的自同构群等。在有限非交换单群上的非正规Cayley图的构造与分类上取得较大突破；系统研究了4-连通齐性图，并证明7-连通齐性图均是连通齐性图，首次开展了3-集合齐性图的研究，相关结果被审稿人认为是该方面研究重大进展的代表性成果；有关图的直积的自同构群的研究，被审稿人认为是对蓬勃发展的图的稳定性研究领域的一项重大贡献。. 在包括JCTA、JCTB、JGT等图与组合领域高水平期刊上发表论文30余篇。