图的对称性与计数研究

Investigating symmetries of graphs, by utilizing finite group theory together with topology, combination and graph methods, has become an active research branch, which has wide applications in many fields such as information science. The project deals with symmetries of graphs, enumerations of graphs and its maps and coverings, by concentrating on algebraic properties and construction properties of graphs. The detailed contents are as following: automorphism groups of graphs, including stabilizers, automorphism groups of symmetric graphs with given orders, normality of Cayley graphs of solvable groups and automorphism groups of symmetric graphs admitting a vertex-transitive non-abelian simple group, by emphasizing some long unsolved problems such as normality of Cayley graphs of prime-power order; construction and classification of graphs with high symmetries, including 1-regular graphs, symmetric graphs with given orders, arc-transitive graphs with small girths and half-arc-transitive graphs, by emphasizing basic graphs and the open conjecture claiming that all half-arc-transitive Cayley graphs of prime-power order are normal; construction and classification of regular covers, including symmetric regular covers of basic graphs with small orders, symmetric regular covers of infinite family basic graphs, half-arc-transitive regular covers, by emphasizing required graphs in classifications of symmetric graphs with given orders and of symmetric Cayley graphs of generalized dihedral groups; enumerations of graphs and maps, by emphasizing regular coverings of graphs, congruence classes of maps of famous graphs, and graphs with given orders and high symmetries under isomorphism.

利用有限群理论，结合拓扑、组合和图论方法研究图的对称性已经成为国际学术界一个活跃的研究分支，在信息科学等众多领域有着广泛应用。本项目研究图的对称性，图及其相关地图和覆盖的计数，重点是图的代数性质和结构性质。具体研究内容如下：图的自同构群，包括点稳定化子、给定阶小度数对称图自同构群、可解群上凯莱图正规性、存在点传递单群的对称图自同构群，重点是其中长期未解决的问题如素数幂阶凯莱图正规性；高对称性图的构造与分类，包括1-正则图、给定阶对称图、小围长弧传递图、半弧传递图，重点是基础图和素数幂阶四度半弧传递凯莱图都正规的公开猜想；正则覆盖图的构造与分类，包括基图为小阶数图的对称正则覆盖、基图为无限类图的对称正则覆盖、半弧传递正则覆盖，重点是给定阶高对称性图分类中和广义二面体群上对称凯莱图研究中需要构造的图类；图与地图计数,重点是图的正则覆盖计数、著名图类的地图同构类计数和给定阶高对称性图的同构计数。

本项目致力于群论在图与网络中应用，取得系列创新成果。正则多面体研究获得突破，国际上正则多面体构造基本都来自几乎单群，由此著名专家Egon和Weiss于2006年提出公开问题，即2^n阶正则多面体研究：本项目构造分类了多个2^n阶正则多面体，发表在群论顶级期刊JGT上，是该方向标志性成果，也是我国研究者在多面体领域完成的仅有的几个成果之一。凯莱图CI-性解决了关键难题，CI-性研究重点之一是初等交换群，在一批学者包括Babai、Conder、Godsil等著名专家努力下证明秩不超过4的初等交换群是CI-群且存在秩大于5的初等交换非CI-群，秩5初等交换群CI-性多年没有解决，是一个公开难题：本项目证明秩5初等交换群是CI-群，发表在组合领域顶级刊物JCTA上，是本方向关键性成果。对称无核m-凯莱图研究取得重要进展，非交换单群上三度对称凯莱图研究已发表文献十余篇，本项目给出分类三度无核对称m-凯莱图算法，由Magma软件实现，不仅推出前人相关成果，而且得到三度对称无核2-凯莱图和弧正则3-、4-、5-、6-、7-凯莱图分类，由此回答了李才恒在PAMS提出的公开猜想，发表在代数组合顶级期刊JACO上。网络泛圈性研究解决了公开猜想，有关著名立方体网络在这方面公开发表文章达30余篇，本项目解决了该网络容错泛圈性，即彻底解决了Tsai于2007年提出的公开猜想，发表在信息科学顶级期刊IS上。本项目还在半弧传递图、点传递非凯莱图、图的正则覆盖、拟半正则对称图、网络外连通度、网络悲观诊断度等方面取得较大进展。本项目资助2次国际会议，成员到国外合作研究6次，国外同行来我校合作研究6次。资助30余人次参加国内学术会议，申请人多次做大会邀请报告，如2019年6月在第八届国际华人数学家大会上做45分钟特邀报告、2019年8月在G2D2国际会议上做大会邀请报告。资助7名博士生和3名硕士生完成学业，发表28篇SCI科研论文。