有向图及网络的曲面嵌入亏格问题的研究

Genera of digraphs and networks on surfaces are the key and core of embedding theory on orientable surfaces. It is a novel content, a rich theory and having a more widely general developed prospect. Carrying out research on these problems has scientific meaning and applied significance. Research on these problems is still at an early stage, so it has a great many problems to solve. We will do a systematic research around the embedding genera of digraphs and networks on orientable surfaces in this project. The detail contents are followings: (1) Study the embedding genera of some kinds of representative graphs as a basis of studying directed embeddability of digraphs. (2) Study on embeddable properties of digraphs on orientable surfaces. (3) Generalizing many kinds of methods for determining genus of a graph on an orientable surface to directed embedding of digraphs and computing embedding genera of digraphs on orientable surfaces. (4) Research on cycle and path embeddability and minimum genera of networks. These qualitative research not only reveals the internal characters of embedding of digraphs and networks on surfaces，but also can serve as an important theoretical basis for further research on the applications of graphs, digraphs and networks.

有向图及网络的曲面上的亏格是有向曲面嵌入理论的核心和关键，它内容新、理论丰富，且有更普遍的发展前景. 开展对该问题的研究具有重要的科学意义和应用价值。目前人们对它的研究尚处于前期阶段，有很多待解决的问题。本项目就是要围绕有向图和网络在可定向曲面上的嵌入亏格进行系统和深入的研究，具体内容为：（1）研究一些具有代表性的图类在曲面嵌入上的亏格，为有向图的有向可嵌入性的研究打下基础. (2）有向图在可定向曲面上的嵌入的性质研究。(3) 推广确定图在可定向曲面上亏格的各种方法到有向图的有向嵌入上；计算有向图在可定向曲面上的嵌入亏格.(4）研究网络的圈，路嵌入性及其最小亏格. 这些定性研究不仅能深刻地揭示有向图及网络的曲面嵌入的内在特征，而且也为今后研究图,有向图和网络的潜在应用提供必要的理论基础.

图的嵌入和网络容错是国际上非常活跃的研究领域，在多重系统和信息安全领域有着广泛的应用。本项目致力于网络的路，圈嵌入性，有向图在可定向曲面的亏格以及网络的容错性，诊断度等的研究，取得了系列创新成果。图的亏格问题是本课题的重点和难点问题之一。在这方面，关于欧拉有向竞赛图，我们证明了有向图的有向嵌入和对应的无向图的面二可着色嵌入的一一对应关系，得到了阶n的完全图存在一种定向使得竞赛图的有向亏格和无向完全图亏格相同的充分必要条件，此结果回答了Bonnington于2002年在组合界顶级期刊 JCTB上提出的一个公开问题。网络容错嵌入是本项目另一个研究重点。本项目对超立方体，折叠超立方体，平衡超立方体等图类，分别研究了边容错圈嵌入和点容错圈嵌入问题。在泛圈性，路覆盖，容错圈嵌入和容错泛圈性方面取得重要进展。如：有五篇文章发表在信息科学顶级杂志Information Sciences上。另外，本项目还在图的群作用，外连通度，网络的g-好邻诊断，条件诊断度和悲观诊断度方面取得一些列理想成果。对一般正则图类的条件诊断度和悲观诊断度的结果是目前得到的仅有的适应多个网络的成果之一。作为结果的推论，我们可以得到Fan等在IEEE Trans. Comput. 上关于星图网络的悲观诊断和Tsai在Inform. Process. Lett.上关于交错群图的悲观诊断等结果。另外，本课题对Berge-Fulkerson猜想进行研究，给出了满足Berge-Fulkerso猜想的某些图类的刻画，推出多个无限类的Snarks关于猜想的正确性。课题的研究结果分别发表在著名SCI刊物Information Sciences, Applied Mathematics and Computation, Journal of Graph Theory等。 本项目部分资助了3次国际会议，其中2014年8月召开的国际数学家大会《组合与图论》卫星会议，300余人参加。2017年6月的《图论与组合网络国际学术会议》来自中国、美国、澳大利亚、以色列和韩国等国117名专家学者参加。资助项目组成员到国外大学进行合作研究或参加国际会议10余次，参加国内学术会议20余次，其中申请人多次做会议邀请报告。资助国外同行来我校合作研究10余次。项目还资助4名博士生5名硕士完成学业。发表SCI科研论文25篇。