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

项目名称： 图的有限定条件的圈问题研究

项目编号： No.11271230

项目类型： 面上项目

立项/批准年度： 2013

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

项目作者： 颜谨

作者单位： 山东大学

项目金额： 46万元

中文摘要： 本项目研究图的哈密顿圈问题、限定圈长的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-因子以及围长的一些存在性条件.

中文关键词： 图；哈密顿圈；2-因子；不交圈；度条件

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

英文关键词： Graph；Hamilton cycle；2-Factor；Disjoint cycles；Degree condition