图与网络的对称性

Symmetry of graph is one of the important research topics in the algebraic graph theory. Interconnection networks are usually modeled as undirected simple graphs, and one of the central issues in designing interconnection networks is to consider the symmetric properties of the graphs. Symmetries in graphs and networks can be measured by using group actions. So, symmetry of graph or network is closely related to the group theory (more specially, the permutation group theory), and hence it has become one of the most important topics in the cross discipline of group theory, graph theory and network theory. . The project that the applicant hold now has achieved some results in the areas of symmetries of graphs, regular maps, enumeration of the isomorphism classes of maps and network theory and so on. By now, 19 relevant papers has been published in some SCI-indexed journals, and the applicant has given 5 presentations in the international conferences.. This project will focus on a few topics relating to normality of Cayley graphs; the construction and classification of graphs with high symmetry; the k(k≥2)-restricted edge-connectivity of networks with high symmetry; the construction and classification of regular maps; and the enumeration and genus distribution of the isomorphism classes of (reflexible) maps.

图的对称性是代数图论的核心内容之一。互连网络的拓扑结构可以用图来表示，而使得网络具有较高的对称性是网络设计的基本原则之一。图与网络的对称性是通过它们的自同构群在其各个对象(如：顶点集合、边集合、弧集合等)上作用的传递性来描述的。由此可见，图与网络的对称性与有限群论(特别是有限置换群论)紧密相关。 从而，使得图与网络的对称性成为群、图、网络三个不同数学分支交叉领域中的一个热点研究课题。. 申请者主持的青年科学基金重点研究了图的对称性、正则地图、地图同构类的计数、网络理论等方面内容。自立项以来，在SCI检索期刊上发表论文19篇，先后在5次国际会议上作相关学术报告。. 本项目将主要致力于以下方面的研究：1. Cayley图的正规性及高对称性图的构造和分类；2.高对称性网络的高阶限制边连通性；3.正则地图的构造与分类及(可反射)地图同构类的计数与亏格分布。

本项目主要开展了以下方面的研究：.一、.图的对称性.利用有限群理论，结合拓扑、组合和图论方法，重点研究了Cayley图及双Cayley图的自同构群、以及一些高对称性图（如点传递非Cayley图、弧(边)传递图等）的构造与分类等，取得了一系列成果。特别地，在有限非交换单群上的5度连通Cayley图的自同构群、双Cayley图的对称性、四度奇素数幂阶边传递图的刻画、边传递几乎自补图等关键性问题上取得了突破性进展。在该方面共发表SCI检索论文11篇。.二、.网络的限制容错分析.在该方面，本项目重点研究了具有较强对称性的几类网络，如平衡立方体网络、折叠立方体网络、类立方体网络等限制容错性能，如外连通度、超连通度、限制连通度、圈边连通度等，在研究方法和研究结果两方面均取得较大突破。在该方面共发表SCI检索论文9篇。