图的对称性及其在网络中的应用

Investigating symmetry of graphs and its applications on networks, by utilizing algebraic theory especially the group theory, together with combinatorial and graph theoretic methods, has become an active research branch in the international academic circles. The project deals with automorphism groups of graphs, CI-property of Cayley graphs, graphs with high symmetries, cycle or path embedding in networks, faulty tolerance of networks, by concentrating on algebraic properties of graphs and their applications on networks. The detailed contents are as following: automorphism groups of graphs, including the structure of stabilizers, normality of Cayley graphs and bi-Cayley graphs, automorphism groups of symmetric graphs and half-arc-transitive graphs with given properties, automorphism groups of frequently used networks and so on; CI-property of Cayley graphs, including CI-property of metacyclic groups, CI-property of elementary abelian groups and so on; graphs with high symmetries, including symmetric Cayley graphs and bi-Cayley graphs on simple groups, edge-primitive graphs, symmetric graphs with small girths, symmetric or half-arc-transitive graphs with given orders or valences and so on; path or cycle embedding in networks, including k-path covers, pancyclicity and fault-tolerant pancyclicity, path-pancyclicity, Hamilton decomposition and so on; faulty tolerance of networks, including restricted connectivity, super connectivity, cycle connectivity， pessimistic diagnosability and so on. The project emphasizes long unsolved problems, such as Weiss conjecture, Babai open problem, Marusic conjecture and so on.

利用代数理论特别是群论，结合组合、图论等方法研究图的对称性及其在网络中的应用已成为国际学术界一个活跃的研究分支。本项目研究图的自同构群、凯莱图CI-性、高对称图、网络圈和路嵌入、网络容错性，重点是图的代数性质及其在网络理论中的应用。具体研究内容如下：图的自同构群包括点稳定化子结构、凯莱图和双凯莱图正规性、给定性质的对称图和半弧传递图自同构群、常用网络自同构群等；凯莱图CI-性包括亚循环群CI-性、初等交换群CI-性等；高对称图包括单群上对称凯莱图和双凯莱图、边本原图、小围长对称图、特殊阶和度数的对称图和半弧传递图等；网络圈和路嵌入包括k-路覆盖、泛圈性和容错泛圈性、路泛圈性和汉密尔顿圈分解等；网络容错性包括限制性连通度、超连通度、圈连通度、悲观诊断度等。重视长期以来未解决的公开问题，特别是 Weiss 猜想、Babai 公开问题、Marusic 猜想等。

利用代数理论特别是群论，结合组合、图论等方法研究图的对称性及其在网络中的应用已成为国际学术界活跃的研究分支。本项目主要研究了图的自同构群，凯莱图CI-性，高对称图，正则多面体和正则地图，网络圈和路嵌入，以及网络容错性。图的自同构群方向：在DRR和GRR问题、Haar图自同构群、(n,k)-排列网络自同构群等方面取得进展，解决了Estelyi-Pisanski公开问题；特别是GRR问题上取得重大突破，完成了任意m-GRR群分类，其中m=1是历史上著名的GRR问题，由权威专家Babai、Godsil等完成。凯莱图CI-性方向：在初等交换p-群CI-性、NDCI-群和NCI-群方面取得进展，解决了Li公开问题；特别证明了秩5初等交换群是CI-群，是该方向标志性成果，秩不超过4初等交换群是CI-群由Babai、Conder、Godsil等完成。高对称性图方向：在双凯莱对称性、单群上对称凯莱图、边本原图、拟半正则对称图、高弧传递图等方面取得进展，解决了Marusic-Sparl等多个猜想；特别完成一定条件下单群上素数度对称凯莱图分类，是该方向关键性突破，由著名专家Praeger等提出。正则多面体和正则地图方向：在Schulte-Weiss公开问题和正则地图分类方面取得进展，正则多面体的研究填补了我国学者在该方向研究的空白。网络圈和路嵌入方向：在网络汉密尔顿性、图的匹配覆盖、树和圈嵌入、控制数、Turan问题等方面取得进展，在多个公开问题上取得突破；特别证明了具有特殊偶圈结构的Snarks Berge-Fulkerson猜想成立，解决了Bonnington公开问题。网络容错性方向：在诊断度、完全独立支撑树、树连通度、限制连通度等方面取得进展，成功应用于网络可靠性分析；特别解决了数据中心网络的条件边容错汉密尔顿性和完全独立支撑树存在性问题，在云计算中有重要应用背景。.发表SCI论文110篇，其中组合领域顶刊JCTA/B上7篇，代数领域顶刊JA上1篇，代数组合领域顶刊JACO上3篇，图论方向顶刊JGT上4篇，群论方向顶刊JGT上3篇。资助4位博后出站，14位获博士学位，10位获硕士学位，在读博士10位；毕业生中6位获国家自然科学基金资助。资助7次国际会议，13次国外专家访华，项目组成员6次国外合作访问、参加学术会议33次。