关于线图和有向图圈结构若干问题的研究

Thomassen in 1986 conjectured that every 4-connetced line graph is hamiltonian, and Caccetta and Haggkvist in 1978 conjectured that every digraph on n vertives with minimum outdegree at least n/r has a directed cycle of length at most r. The two conjectures are still open and many related problems were posed by reseachers. In this project we consider two of them: what is the smallest integer k such that a 3-connected and essentially k-connected line graph is hamiltonian, and does a digraph on n vertives with minimum outdegree and indegree at least n/r has a directed triangle. Moreover, we also consider several related problems of the two problems mentioned above, such as, the circumferences in the line graphs and claw-free graphs, pancyclicity of line graphs, and the girth of digraphs and so on. The project focus on topics on hamiltonicity of line graphs, supereulerian graphs, connectivity of graphs and cycles in digraphs. Thus, the methods such as the closure method of line graphs, the reduction method of supereulerian graphs, atom theory on the connectivity of graphs, and the well-known Regularity Lemma will be used.

Thomassen 1986年猜想"4-连通线图是哈密尔顿的"；Caccetta和Haggkvist 1978年猜想"出度不小于n/r的有向图包含长度不超过r的有向圈"，其中n为图的顶点数，r为正整数。这两个猜测至今未被解决且引申出诸多研究课题，本项目关注如下两个问题，其一，能够保证3-连通线图是哈密尔顿的最小的本质连通度是多少？其二，出度和入度均不小于n/3时的有向图是否包含有向三角形？这两个问题均是可扩展的，对它们的深入研究将引申出诸多后继课题，比如线图的哈密尔顿连通性，线图的周长，线图泛圈性和子泛圈性，以及有向图的围长等问题。上述问题一及其相关问题是本项目的研究核心。 项目课题主要涉及图的哈密尔顿性，超欧拉性，连通性，有向图的圈等，所使用的主要图论方法为线图闭包方法，Catlin的收缩方法，图连通性的原子理论，以及 Regularity Lemma等。

Thomassen 1986年猜想“4-连通线图是哈密尔顿的”；Caccetta和Haggkvist 1978年猜想“出度不小于n/r的有向图包含长度不超过r的有向圈”，其中n为图的顶点数，r为正整数。这两个猜测至今未决，同时也引申出来诸多研究课题。项目组对预设研究问题进行了系统研究，在有向图和线图圈结构研究上取得了较丰富的进步；其中，基于边度和条件考虑Thomassen猜想，基于Chavatal-Erdos条件考虑了图的欧拉性，基于最小度条件考虑线图生成子图的哈密尔顿性，探索了有向图上的Caccetta-Haggkvist猜想和特殊有向图的圈结构；研究团队建设取得了一定进步，在项目研究的基础上申报国家自然科学基金面上项目一项；在本项目资助下学术交流频繁，其中主办学术会议2场。