图的超欧拉性与线图和稠密图的圈结构若干问题研究

Determining whether a graph is supereulerian (or hamiltonian) is NP-complete, and the problem is a classic topics in graph theory. In 1979, Jaeger showed that every 4-edge-connected graphs is supereulerian, but the characterization of supereulerian 3-edge-connected graphs is still open. In 1986, Thomassen conjectured that every 4-connected line graph is hamiltonian. A line graph L(G) has a hamiltonian cycle if and only if the graph G has a dominating closed trail. Thus, the dominating closed trails (and spanning tails) play an important role in the study of the hamiltonicity of line graphs. This project considers the hamiltonian cycle and edge-disjoint hamilonian cycles of line graphs under the restriction of connectivity, the spanning trails and dominating trails of graphs under restriction of edge-connectivity, and the relationship of the two topics; and we shall also consider the hamiltonicity of dense graphs by using the regularity lemma.

图的生成迹存在性（超欧拉性）和哈密尔顿圈存在性（哈密尔顿性）是两个NP-完全问题，研究图的超欧拉性和哈密尔顿性及其相关问题已经发展成为图结构理论的两类经典课题。Jaeger在1979年证明4-边连通图是超欧拉的，那么刻画3-边连通图（2-边连通图）的超欧拉性就自然成了厄待解决的问题；Thomassen猜想（4-连通线图是哈密尔顿的）及其相关研究是线图圈结构领域热点之一。线图圈结构问题研究往往转化到原图的迹问题，那么研究基于连通性限制下的线图的圈结构并同时研究基于边连通性限制下图的迹是一种比较自然的研究思路。本项目研究连通度（与最小度）条件下线图的哈密尔顿圈和边不交哈密尔顿圈存在性；研究边连通度等条件下图的生成迹/控制迹存在性，及其与线图哈密尔顿圈、泛圈和边不交哈密尔顿圈的关系；另外，研究基于Dirc条件下稠密图的特定哈密尔顿圈的存在性是本项目的另一个重点问题。

线图的圈结构图的圈结构领域一个经典有趣的研究方向，其问题研究往往转化到原图的迹问题，那么研究基于连通性限制下的线图的圈结构并同时研究基于边连通性限制下图的迹是一种比较自然的研究思路。此项目研究重点是探索线图的哈密尔顿圈和边不交哈密尔顿圈存在性；探索基于高边连通度等条件下图的特定生成树与生成迹存在性，及其与线图哈密尔顿圈、泛圈和边不交哈密尔顿圈的关系；在图圈结构研究中，基于高连通度或者大的最小度条件是一个较为基本的条件，此项目的另一个研究出发点是探索点数较多稠密图的圈结构。..研究期间项目组深入研究了原图的迹与线图边不交哈密尔顿圈数量对应，给出了基于最小度条件下的线图边不交哈密尔顿圈存在数量下届；基于hopping思想给出了哈密尔顿连通线图任何两点之间不交哈密尔顿路的一个数量下届；作为线图的一个导出子图，Gallai图是一个老的概念，项目组Gallai图的刻画进行了一定的探索；对迭代线图的哈密尔顿路存在性指数给出了刻画；对有向图的生成连通度（哈密尔顿连通性与连通性的融合）进行了定义，并给出了竞赛图的生成连通度下届研究；对二部竞赛图的anti-哈密尔顿圈进行刻画，得到了几类充分条件；基于对Enomoto猜想稠密图上存在哈密尔顿圈使得一对点距离为指定距离在大图上的证明，推广到对Faudree and Li的猜想在充分大图上的证明。同时，在项目开展过程中对图的minor、图的染色、平面图的子哈密尔顿性等相关问题进行探索。