学位论文 > 优秀研究生学位论文题录展示

两类特殊图类的路和圈问题

作　者: 沈雷
导　师: 王江鲁
学　校: 山东师范大学
专　业: 应用数学
关键词: (K1,4 2)-图半无爪图邻域并完全圈可扩 Hamilton性 (齐次)可迹性
分类号: O157.5
类　型: 硕士论文
年　份: 2008年
下　载: 27次
引　用: 3次
阅　读: 论文下载

内容摘要

图的路和圈问题是图论中一个十分重要而且活跃的研究课题，有大量的实际问题可以归结为图的路和圈问题．图论中三大著名难题之一的Hamilton问题本质上也是图的路和圈问题．国内外许多学者对此问题作了大量的研究工作．这方面的研究成果和进展可参见文献[40]-[43].其中度条件和邻域并条件成为研究路和圈问题的重要途径，在这方面取得了很多优秀的成果．经过几十年的发展，图的路圈性质所涉及的内容日益丰富和具体．路的方面包括图的Hamilton-路（可迹性），齐次可迹性，最长路，Hamilton-连通，泛连通，路可扩等等；圈的方面包括图的Hamilton圈，最长圈，（点）泛圈，完全圈可扩，点不交的圈，圈覆盖等等．由于直接研究一般图的Hamilton问题往往比较困难，于是人们转而研究不含有某些禁用子图的图类．继Beineke1968，1970年发表的关于线图性质的两篇文章[16]-[17]之后，人们开始关注包含着线图的无爪图．70年代末80年代初，是研究无爪图的一个非常活跃的时期．关于无爪图方面的部分优秀成果可参考[2]-[4]，[18]-[33]．另外，无爪图的概念也被从不同角度推广到了更大的图类，如半无爪图，几乎无爪图，(K_1，4；2)-图，DCT图等．1998年，A．Ainouche在[35]中定义了一种包含无爪图的更大的图类-半无爪图，且给出了关于半无爪图的路和圈方面的一些结果．之后，很多专家学者相继做了大量的工作来研究这类图Hamilton问题且将无爪图中的许多非常好的结果推广到了半无爪图．其中某些进展可参考[36]-[38]．2003年，滕延燕，尤海燕，蔺厚元等在无爪图的基础上提出了K₁₄-受限图的概念(后者称之为(K_1，4；2)-图)，它包含无爪图类，并且无爪图的很多结果可以推广至(K_1，4；2)-图．本篇论文主要研究了半无爪图，(K_1，4；2)-图的路和圈问题．在第一章中，我们主要介绍文章中所涉及的一些概念和术语符号，以及本文的研究背景和已有的一些结果．在第二章中，我们主要研究了三角连通的(K_1，4；2)-图完全圈可扩性，得到下面的结果：定理2．4顶点数不小于3，无孤立点，爪心独立的三角连通(K_1，4；2)-图是完全圈可扩的．在第三章中，讨论了半无爪图在不同连通度下关于路和圈的几个结果：定理3．2．4设G是阶为n≥3的连通半无爪图，如果对任意不相邻的顶点x，y，都有2|N（x）∪N（y）|+d（x）+d（y）≥2n-5成立，则G是可迹的．推论3．2．5设G是阶为n≥3的连通半无爪图，如果对任意不相邻的顶点x，y，都有|N（x）∪N（y）|≥2n-5/3，则G是可迹的．定理3．3．5设G是阶为n≥3的2-连通半无爪图，如果对每对不相邻的顶点x，y有2|N（x）∪N（y）|+d（x）+d（y）≥2n-5，则G是Hamilton图．推论3．3．6设G是阶为n≥3的2-连通半无爪图，如果对任意不相邻的顶点x，y，都有|N（x）∪N（y）|≥2n-5/3，则G是Hamilton图．定理3．4．2设G是阶n≥3的3-连通的半无爪图，若对G中任意3个顶点的独立集{x1，x2，x3}，有d（x₁）+d（x₂）+d（x₃）≥n+1，则G是Hamilton-连通图．定理3．5．3设G是一个阶为n（n≥3）的2一连通半无爪图，连通度为k．（1）如果对于每一个k+1个点的独立集S，对任意u，v∈S，都有|N（u）∪N（v）|≥2n-3k+1/3，则G是Hamilton图．（2）如果对于每一个k+1个点的独立集S，对任意u，v∈S，都有|N（u）∪N（v）|≥n-k-△_S，则G是Hamilton图．在第四章中，研究了半无爪图不含禁用子图H时的齐次可迹性，证明了下面的结果：定理4．3 G为直径至多为3的2-连通的半无爪图，若G不含同构于H的导出子图，则G为齐次可迹的．

全文目录

中文摘要  5-7
英文摘要  7-10
第一章预备知识  10-15
  1.1 符号概念介绍  10-12
  1.2 研究背景及已有结果  12-15
第二章 (K_(1,4);2)-图的完全圈可扩性  15-18
第三章半无爪图的度条件和邻域并条件  18-35
  3.1 半无爪图的两个重要性质  18-19
  3.2 连通半无爪图的可迹性  19-23
  3.3 2-连通半无爪图的Hamilton性  23-28
  3.4 3-连通半无爪图的Hamilton-连通性  28-32
  3.5 连通度为七半无爪图的Hamilton性  32-35
第四章半无爪图的齐次可迹性  35-39
参考文献  39-43
攻读学位期间发表的学术论文  43-44
致谢  44

两类特殊图类的路和圈问题

内容摘要

全文目录

相似论文