超欧拉有向图及欧拉连通有向图的研究

In recent years, the research on graph theory has already appeared the tendency of extremely activity with the computer science and network technology development, and supereulerian theory has become one of the developing fields within graph theory. As a new and important research field in graph theory, supereulerian digraph has extensive application in related fields. Compared with the study of the supereulerian graph, the supereulerian digraph has the strong application background, it is still in its infancy. Thus, there are still many problems worth of exploring and mining. In this project, we choose the supereuleruian digraph with given diameter as the main starting point of our research, we will study the sufficient condictions on the digraph for making various operations to be supereuleruian digraph, and explore the supereulerianity of digraph with the special relationship between arc-strong connectivity and matching number, independent number. Moreover, we will discuss the eulerian-connectivity of tournament, symmetric connected digraph and partial symmetric connected digraph. The research contents and results of the project will provide cogent reference data for application in Engineering, enrich the results of the supereulerian theory of graphs and digraphs, and provide the necessary research experience and mode of thinking for further research on the supereuleruianity and eulerian-connectivity of general digraphs.

近年来，随着计算机科学和网络通讯技术的发展，图论研究也呈现出异常活跃的趋势，而超欧拉理论的研究是近阶段发展的几个领域之一。超欧拉有向图作为图论的一个新型且重要的研究方向，在相关学科领域具有广泛的应用。相对于无向图的超欧拉性研究，有向图的超欧拉性有较强的应用背景且起步较晚，因此，还有很多问题值得去探索和挖掘。本项目选择在直径条件下有向图的超欧拉性研究作为我们的研究基点，研究有向图做不同种运算后成为超欧拉有向图的充分条件，探索有向图的弧连通度与匹配数、各种独立数之间的特定关系下，有向图的超欧拉性，同时研究竞赛图、对称连通有向图、偏对称连通有向图等的欧拉连通性。通过以上内容的研究，力争完善有向图的超欧拉性与欧拉连通性的研究体系。本项目的研究内容将会为工程应用提供有力的参考数据，同时丰富图与有向图的超欧拉性的理论成果，为我们进一步研究一般有向图的超欧拉性与欧拉连通性提供必要的研究经验和方法思路。

近年来，随着计算机科学和网络通讯技术的发展，图论研究也呈现出异常活跃的趋势，而超欧拉理论的研究是近阶段发展的几个领域之一。超欧拉有向图作为图论的一个新型且重要的研究方向，在相关学科领域具有广泛的应用。相对于无向图的超欧拉性研究，有向图的超欧拉性有较强的应用背景且起步较晚，因此，还有很多问题值得去探索和挖掘。本项目主要研究了有向图的超欧拉性及连通性相关问题。本项目围绕Bang-Jensen和Thomassé猜想：“如果一个有向图D的弧连通度大于等于点独立数，则有向图D是超欧拉有向图。”以及Algefari等人证明的结果“如果一个有向图的弧强连通度大于等于最大匹配数，则有向图是超欧拉有向图”，做了如下研究：在给定的弧强连通度与最大匹配数的关系情况下，保证有向二部图是超欧拉的。给出了3-路-拟可迁有向图成为超欧拉有向图的充分必要条件并且证明了这个猜想对于3-路-拟可迁有向图而言是正确的。其次，介绍了对称核的概念，证明了收缩有向图可以用来判断有向图中生成迹的存在性。利用对称核的概念证明了在匹配数满足一定条件的情况下，保证有向图有生成迹、是超欧拉有向图及是强迹连通的。另外，我们还利用四种不同的度和条件的情况，证明了有向图是超欧拉的。研究了直径条件下有向图的超欧拉性：证明了直径小于等于2有向图都是超欧拉的。发现了存在无限多直径为3的非超欧拉有向图。并证明了直径小于等于3的二部有向图的超欧拉性。研究了有向图的笛卡尔积有向图、强积有向图、字典式积有向图、幂有向图、l-路和图等的超欧拉性。研究了具有禁止诱导特殊短有向路的超欧拉以及有向图一类超欧拉有向图中的超欧拉bypass性质和字典式积有向图及正则一致m-部竞赛图中D(n，p)结构。研究了竞赛图、对称连通有向图、偏对称有向图的强迹连通及弱迹连通性。本项目的研究内容为工程应用提供有力的参考数据，同时丰富图与有向图的超欧拉性的理论成果，为我们进一步研究一般有向图的超欧拉性与欧拉连通性提供必要的研究经验和方法思路。. 本项目共计发表相关学术论文21篇，其中SCI收录9篇。项目组共计培养硕士研究生27名，项目组成员1人晋升为教授，1人晋升为副教授，1人取得博士学位。并且和国内、外专家建立了交流合作基础并多人次参加学术会议。