基于凯莱图的互连网络有效控制集与自同构群研究

With the rapid development of a new generation of information technology industry, how to optimize and design interconnection networks becomes a very important topic. Cayley graphs are widely used as models for interconnection networks due to their good properties.The project mainly studies the efficient dominating sets and automorphism groups of interconnection networks based on Cayley graphs. Applying the methods and techniques of combinatorics, graph theory and finite group theory, we investigate the existence of efficient dominating sets in Cayley graphs of abelian group including circulant graphs, Cayley graphs of symmetric groups and alternating groups, give the sufficient condition or necessary and sufficient condition for admitting efficient dominating sets, and characterize all efficient dominating sets if exist. For some important Cayley graphs of symmetric groups and alternating groups, using the tools of graph theory and permutation group theory, we characterize their automorphism groups basing on the understanding towards their structure features. The expected research results of this project will optimize effectively the design, information dissemination and resource allocation and placement of interconnection networks, and also investigate the symmetry of interconnection networks. Research methods in this project will develop new ideas on the study of efficient dominating sets and automorphism groups of Cayley graphs.

随着新一代信息技术产业的飞速发展，如何优化与设计互连网络成为一个非常重要的课题。凯莱图由于具备良好的性质被广泛用来作为互连网络的模型。本项目主要研究基于凯莱图的互连网络的有效控制集和自同构群。运用组合论、图论及有限群论的方法和技巧，考察交换群上的凯莱图包括循环图、对称群与交错群上的凯莱图的有效控制集的存在性，给出有效控制集存在的充分或充要条件，并刻画存在时的所有有效控制集。针对对称群与交错群上的某些重要凯莱图，利用图论和置换群论的工具，基于对它们的结构特征的把握来刻画出其自同构群。本项目的预期研究成果将有效优化基于凯莱图的互连网络的设计、信息传播与资源配置，并能考察其对称性的优劣。项目的研究方法将拓宽对凯莱图有效控制集及自同构群的研究思路。

凯莱图由于具备良好的性质被广泛用来作为互连网络的模型。通过运用图论及有限群论的方法和技巧，本项目研究了基于凯莱图的互连网络的有效控制集和自同构群。首先，给出了任意循环图存在有效（开）控制集的充要条件，并给出了存在时的所有有效（开）控制集构成的集合的上下界范围，再附加一定的条件，如特定的控制数或度数，刻画了存在时的所有有效控制集；进一步给出了交换群上满足一定条件的凯莱图存在有效开控制集的充要条件；另外，给出了任意顶点子集构成某个循环图的有效（开）控制集的充要条件。其次，作为星图和烙饼图的推广，定义了对称群上的一类凯莱图，并考察了它们的有效控制集的存在性，找出了它们的一些有效控制集，从而得到了它们的控制数；也推导出了它们的顶点子集构成有效控制集的一些必要条件。最后，刻画了交错群上的两类重要凯莱图的自同构群，也刻画了对称群上的两类凯莱图即冒泡排序星图和轮对换图的自同构群。项目的研究成果能有效优化基于凯莱图的互连网络的设计，项目的研究方法拓宽了凯莱图有效控制集和自同构群的研究思路。