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

项目名称： 关于线图和有向图圈结构若干问题的研究

项目编号： No.11301371

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 数理科学和化学

项目作者： 杨卫华

作者单位： 太原理工大学

项目金额： 23万元

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

中文关键词： 线图；哈密尔顿圈；欧拉性；连通度；有向图

英文摘要： 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.

英文关键词： Line graphs；Hamiltonian cycles；Supereulerian graphs；Connectivity；Digraphs