图中长圈和路及相关问题研究

图的哈密尔顿性的研究是图论中最基本的问题之一，已有较长的历史，近几十年来一直受到图论学家的广泛关注，取得了许多深刻的结果，同时在图的哈密尔顿性问题及相关领域中又出现了许多有重要意义的待解决的问题。本项目将综合运用图论、组合论代数学及概率论的方法，深入探讨图的哈密尔顿性及和图中圈路相关的问题。将致力于图中满足各种条件的圈和路的存在性条件的研究，研究一般图及满足一定条件的一些重要图类的结构，力争在图的哈密尔顿性及与圈路相关的问题上取得实质性的进展。

依照申请书的研究内容和计划，开展了相关的研究，基本上完成了预定的研究任务。研究的主要内容图中圈路问题，包括图的哈密尔顿性问题，某些特定结构（圈路等）的存在性条件，特殊图类（如线图、无爪图及P3-支配图等）和图运算（笛卡尔乘积、直积以及一些广义乘积等）中的圈路问题和连通性问题以及一些重要参数的确定问题等。项目组三年中完成研究论文10余篇，发表（其中3篇已接受即将发表）标注有本项目资助的论文共10篇，其中SCI收录杂志上7篇，国际性杂志上2篇，1篇在国内杂志上。三年中共有6名硕士研究生毕业，现有在读硕士研究生7其中两名硕士研究生将于2014年毕业。我们的成果有以下几个方面。.无爪图和P3-支配图的圈性质，包括P3-支配图的m-支配圈存在性条件，哈密尔顿性的邻域并条件以及五爪图的哈密尔顿性的禁止子图条件等。.树图、单圈图及一类特殊图的哈密尔顿连通指标的确定，得到了这几类图的这个指标的表达式或紧的上下界。.证明了当k大于等于3时一个至少有k+1个顶点的图的k次方幂是k-生成连通的，是已有关于图方幂的哈密尔顿性质的推广。.研究了一类笛卡尔乘积图的哈密尔顿连通性问题，得到了他们是哈密尔顿连通的充要条件，并得到了柱图是3-生成连通的一个充分条件。另外，给出了一般图和完全图的直积的边连通度的精确表达式以及两个图直积的边连通度的一个估计式。