半对称图的分类与刻画

Transitive graph is an important and active research object in algebraic graph theory, whose symmetry is reflected by the transitive action of the automorphism group on the corresponding elements of the graph. Symmetric graphs are not only closely related to algebra, geometry, topology and combinatorics in mathematics, but also widely used in information science, coding theory, cryptography, biology, chemistry, computer science and so on. The semisymmetric graph is regular, edge-transitive and not vertex-transitive, which is an important family of transitive graphs. The study of such graphs has important theoretical significance and application value. In this project, through the action of automorphism group on the graph, mainly based on permutation group theory and finite group theory, using the methods of topological graph theory and combinatorial graph theory, combined with computer software to carry out the research. This project aims to enrich the results of semisymmetric graphs, provide methods and ideas for permutation groups on combinatorial structures, explore the application on algebraic coding and promote a deeper understanding of permutation groups in the research process.

传递图是代数图论中一个重要且热门的研究对象，其对称性是由图的自同构群在图上相应元素传递作用来体现的。对称图不仅与数学中代数、几何、拓扑以及组合数学有紧密联系，还在信息科学、编码理论、密码学、生物学、化学、计算机科学等学科有广泛的应用。半对称图是边传递且非点传递的正则图，是传递图中一类重要的图类，此类图的研究具有重要的理论意义和应用价值。本项目将通过图自同构群在图上的作用，以置换群理论和有限群论为主，利用拓扑图论以及组合图论的方法，结合计算机软件辅助来展开研究。本项目旨在丰富半对称图的结果，为置换群在组合结构上的研究提供方法和思路，并探索置换群在代数编码上的应用，同时在研究过程中促进对置换群更深刻的了解。

本项目以解决Folkman在1967年提出的公开问题为目标，通过置换群在图上的作用，结合图论方法以及群论工具，研究了2倍素数幂个顶点的半对称图。首先，我们给出判定正则边传递图是顶点传递图的一个充分条件和判定正则边传递图是半对称图的三个充分条件，这为研究一般半对称图增添了更多的判定工具。其次，应用这些判定条件，我们给出了2p^4个顶点的p度半对称图的分类并构造了一类2p^n个顶点的p度半对称图。在研究中我们尝试对图的自同构群进行刻画，并代替自同构群运用其西罗p-子群来构造半对称图，这对于半对称图的研究是一个新的尝试。 最后，我们研究了凯莱图的直积图的正规性，给出凯莱图的直积图是正规凯莱图的充分必要条件以及给出一些非交换群上小度数双凯莱图的完全分类。在此基础上，我们还努力探索置换群和图论在编码和密码中的应用，比如凯莱图上perfect码的相关问题。在项目资助下，项目组成员参加了6个学术会议，申请人做2次大会邀请报告。本项目按原计划顺利执行，项目成果正在整理2篇，已投稿1篇。