图的有限定条件的圈问题研究

This project studies the following three kinds of cycles: Hamilton cycles,2-factors with specified cycle-lengths, and girths in graphs. (1) Thomassem conjectured that every 4-connected line graph is Hamiltonian, Matthews and Sumner conjectured that every 4-connected claw free graph is Hamiltonian. We consider the conjectures and investigate the properties of k-connected (k=3,4) line graphs and claw-free graphs, such as the existence of Hamilton cycles, Hamilton-connected graphs and s-Hamilton graphs etc; (2) We shall generate Erd?s and Faudree's conjecture concerning 2-factors with 4-cycles, that is, we consider 2-factors with specified cycle-lengths on the condition of minimum degrees, Ore-condition, Fan-condition and neighborhood condition in graphs. The conditions of 2-factors in K-partite graphs and claw free graphs are also investigated; (3) In this project, the girths in directed graphs are also studied, we want to approach Caccetta-H?ggkvist conjecture. By studying the stucture of graphs, we hope to prove a few conjectures, and then obtain the conditions of Hamilton cycles,2-factors and girths in graphs.

本项目研究图的哈密顿圈问题、限定圈长的2-因子问题和有向图的围长问题.（1）Thomassen猜想每一个4-连通的线图是哈密顿的,Matthews and Sumner猜想每一个4-连通的无爪图是哈密顿的. 围绕猜想我们主要研究k-连通（k=3,4）线图和无爪图的哈密顿性、哈密顿连通性、s-哈密顿性等，使猜想有更多实质性进展并努力证明猜想；（2）Erd?s和Faudree猜想在一定最小度条件下图有一个2-因子含k个4-圈，我们研究此猜想的一般情况，即研究图有一个2-因子含k个任意指定长度的圈的最小度条件、Ore-条件、范-条件以及邻域条件等，此外研究k-部图或无爪图的2-因子存在性；（3）研究有向图的围长问题，努力使Caccetta-H?ggkvist猜想有更多进展.通过研究图的结构，证明几个猜想，从而找到哈密顿图、2-因子以及围长的一些存在性条件.

图中的圈问题是图论研究的经典问题，本项目主要研究图中有限定条件的圈问题，主要研究了图、二分图、无爪图、有向图的圈问题，研究的条件有最小度条件、Ore -条件、部分度和、范-型条件、连通度以及极值参数条件等。具体研究要点可归纳如下：首先，对于图中 k个不交圈的问题，我们得到了两种新型条件，即距离为2的点度和条件和范-型条件，这是对本方向的奠基性定理“Corrádi- Hajnal 定理”的广义性推广。同时我们研究了图及二分图含指定性质的不交圈问题，部分回答了Wang猜想，这也是对Erdös和Bollobás 所研究的因子问题的进一步探索。我们还研究了图与无爪图的哈密顿性，并且围绕 Erdös-Faudree 关于2-因子的猜想，研究了任意的2-因子问题，包括含任意分支数的2-因子和每一分支指定点数的2-因子，得出了一系列结果。更进一步地，围绕Bermond 和Thomassen 关于有向图中圈的猜想，我们考虑了有向图的小圈问题。最后我们延伸研究了图的不交子图问题，利用Ramsey数证明了Fujita 猜想在大部分情况下成立。