图中结构与全局参数

图中结构是图论研究的一个热点，对其进行研究不但有重大的理论意义，而且在理论计算机科学、生命科学、管理科学和运筹学中有很强的应用背景。本项目拟从独立数、连通度、坚韧度这三个图中全局参数出发对图中圈型结构和哈密尔顿连通性进行深入探讨。我们将通过对独立数一定的k-连通图结构的精确分析研究图的周长与连通度和独立数的关系；通过引入一些新的方法和闭包、超图、超树方面的技巧研究无爪图的哈密尔顿性和哈密尔顿连通性；将图的整体性质与局部性质相结合，并利用坚韧度与圈结构研究的最新方法和技巧,试图深入探讨某些特殊图类的坚韧度与哈密尔顿性之间的关系。本项目的研究将推进Fouquet和Jolivet关于图的周长与连通度和独立数关系猜想、Matthews 和Sumner关于 4-连通无爪图的哈密尔顿性猜想以及Chvátal关于图的坚韧度与哈密尔顿性猜想的早日解决，有利于我国图论研究与世界进一步接轨。

图中结构是图论研究的一个热点。本项目利用连通度、独立数和两分结合数等图中全局参数对图中结构进行了深入探讨，在k-连通图的周长、无爪图的哈密尔顿性、二部图的泛圈性、图中路型结构与坚韧度的关系、图谱以及图中结构的代数特征等方面取得重要进展, 共发表研究论文30篇，其中28篇被SCI收录。主要结果如下：(1) 对Fouquet-Jolivet 猜想进行了卓有成效的探讨，建立了图的周长与连通度和独立数的密切联系, 相关论文在Journal of Graph Theory 68 (2011) 55-76上发表; (2) 对二部图的Hamilton性和偶泛圈性进行了深入探讨，提出了“两分结合数”的概念，证明了Woodall猜想的最佳二部图版本：任何两分结合数大于3/2的平衡二部图均为偶泛圈图，相关论文在SIAM Journal on Discrete Mathematics 27 (2013) 597-618上发表；(3) 对无爪图的哈密尔顿性与连通度、禁用子图的关系进行了探讨，在SCI期刊发表论文2篇，证明了3-连通{K(1,3), N(i,j,k)}-free图的哈密尔顿性, 其中i,j,k为任意满足i+j+k=9的正整数；(4) 对图中路型结构与坚韧度的关系进行了探讨, 证明了对任何不含4阶导出路的1-坚韧图G都存在一临界整数s，使得G中任何阶数小于s的路都是可扩的，并且G中存在阶数为s和|G|-1之间的任意整数的非可扩路，相关结果在Discrete Mathematics 312 (2012)上发表； (5) 对图的各类谱和图中结构的其它几类代数特征进行了深入探讨， 在 Graphs and Combinatorics, Linear Algebra and Its Applications, Applied Mathematics Letters 等SCI期刊发表论文21篇。