论文部分内容阅读
哈密尔顿问题一直是图论中近几年来研究的一个热点,这从国际上几种著名的数学刊物及国内几种核心数学期刊发表的文章可见一斑。判断一个图在什么条件下是一个哈密尔顿图即所谓的哈密尔顿问题。而禁用子图的哈密尔顿问题是哈密尔顿问题研究重要的研究领域之一。无爪图(claw-free graphs)是禁用子图研究最为深入的一个图类。关于无爪图的哈密尔顿问题,目前已有很多出色的且较为成熟的结果。同时与无爪图相关的且比无爪图更广的图类-如几乎无爪图(almostclaw-free graphs)、半无爪图(quasi-ckaw-free graphs)的研究更是方兴未艾,新的结果层出不穷。
本文采用“强思维”与“弱思维”的方式首次研究了一种比无爪图更广的图类Y<,3>V<,3>-free图的哈密尔顿问题,这些结果拓展了哈密尔顿问题的研究。
首先本文在第二章第一节研究了在连通、局部连通条件下Y<,3>V<,3>-free图的哈密尔顿性。在连通局部连通条件下存在Y<,3>V<,3>-free图是非哈密尔顿图;甚至存在连通度、局部连通度任意大的Y<,3>V<,3>-free非哈密尔顿图。图的最长圈的研究常常会促进图的哈密顿性的研究。进一步研究Y<,3>V<,3>-free图的最长圈得到本文的第一个重要结果(第二章第一节):定理 1.1.1 若G是顶点数不小于3的连通、局部连通Y<,3>V<,3>-free图,则G的最长圈为控制圈,且G是局部泛圈图(subpancyclic graphs)。
本文在第二章第二节接着探讨在连通局部连通条件下Y<,3>V<,3>-free图成为哈密尔顿图的条件。得到了下面的结果(第二章第一节):定理2.1.2顶点数不小于3的连通、局部连通Y<,3>V<,3>-free、爪心独立图是完全圈可扩的。并得到了下面的两个推论:推论 2.1.1顶点数不小于3的连通、局部连通Y<,3>V<,3>-free、几乎无爪图是完全圈可扩的。推论2.1.3顶点数不小于3的连通、局部连通Z<,1>-free、几乎无爪图图是完全圈可扩的。
这些定理与推论是本文的第二个重要结果,它给出了几乎无爪图是完全圈可扩图的两个充分条件,比较经典的充分条件是Zdenek Ryjacek给出的,见下面的定理:定理若G是顶点数不小于3的连通、局部连通K<,1,4>-free、几乎无爪图则G是完全圈可扩图。
闭包方法是解决哈密尔顿问题的重要手段和方法。本文最重要的创造性工作在于一种无爪图闭包的构造及一种Y<,3>V<,3>-free图类的闭包构造与稳定性讨论。在97年Zdenek Ryjacek定义了无爪图中的一种闭包概念,解决了无爪图中的一系列哈密尔顿问题。设计一种无爪图中比Zdenek Ryjacek闭包更多边的闭包是哈密尔顿问题闭包研究一个努力的方向。Zdenek Ryjiacek闭包的构造着眼于局部连通点增加边。本文在此基础上同时着眼于一定条件下的局部不连通点,构造了一种无爪图中比Zdenek Ryjacek定义的闭包更强(增加更多边)的闭包,并证明了保持周长不变且是唯一的。本文的第三章第二节从缩小加边范围出发构造了一种比无爪图更广图类Y<,3>V<,3>-free图的闭包并进行了一些稳定性讨论。
本文第四章研究了半无爪图泛圈的一种充分条件。半无爪图作为比无爪图更广的图类是由Ainouche在98年首次提出,目前已有较多的研究结果。本文的结果可作为半无爪图泛圈研究的一个丰富与补充。