有限群的凯莱和图与幂图

Graphs associated with groups are related to automata theory and have appeared in various applications, as diverse as construction of larger networks, design of interconnection networks, data mining and combinatorial optimization. This project studies Cayley sum graphs and power graphs of finite groups. The main contents are as follows: study Hamiltonicity of a Cayley sum graph; investigate finite groups with higher genus power graphs; characterize all finite groups have the property that the power graph is connected when the identity is removed.

定义在群上的图不仅跟自动化理论相关，而且在大型网络的构造、互连网络设计、数据挖掘、组合优化等领域都有广泛的应用.本项目主要围绕有限群的凯莱和图与幂图展开如下三方面的研究：研究凯莱和图的哈密顿性；研究具有高亏格幂图的有限群；刻画所有删除单位元后的连通幂图.

众所周知，群的凯莱图具有悠久的研究历史和丰富的研究成果。为了研究图的直径与特征值之间的关系，美国艺术与科学院院士金芳蓉首次引入了交换群上的凯莱和图。此外，作为群上的一个组合性质，群的幂图被介绍，近二十年来，关于群幂图的研究十分活跃。本项目主要围绕有限群的凯莱图、凯莱和图及幂图得到了如下重要结果：（1）分类了定向与非定向亏格为2的幂图所对应的所有有限群。（2）证明了给定一个正整数，存在有限个有限群使得它们的非循环图的亏格为该正整数。利用这个结果，完全分类了非循环图的亏格小于等于4的所有有限群。（3）给出了幂图Lambda数的上下界且完全刻画了幂图的真连通数。（4）刻画了群增大幂图以及简化幂图的强度量维数，也刻画了群增大幂图的度量维数。（5）研究了凯莱图与凯莱和图的完备码问题。给出了子群成为完备码的充分必要条件且找到了广义四元数群的所有子群完备码。凯莱图与凯莱和图完备码方面的研究在信息论、计算机科学及密码学方面具有良好的应用前景。