拟无爪图和K<,1,2>-扩展图的哈密顿问题

来源 :山东师范大学 | 被引量 : 0次 | 上传用户:caojun3538073
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的哈密顿问题是图论学科一个十分重要而且又十分活跃的研究课题,历史也很悠久,每年都有大量关于这一问题的学术论文.但是,由于直接研究一般图类的哈密顿问题比较困难,因此,当前,图的哈密顿问题研究的一个重要方面是在一些特定领域展开.关于哈密顿问题的一些研究进展可参考[23]-[25].继Beineke1968,1970年发表的[10]-[11]之后,人们开始关注起包含着线图的无爪图.70年代末80年代初,是研究无爪图的一个非常活跃的时期,这一时期,涌现了大量优秀的成果.其中,关于匹配性质的可参考[12]-[14].较早关于无爪图哈密顿性质的可参考[15]-[18].关于多项式时间内确定独立数的可参考[19][20].关于Berge的完美图猜想在无爪图中的证明可参考[21].[22]是关于无爪图的综述性的文章,从中我们可了解到关于无爪图的研究进程.另外关于无爪图中取得的优秀成果的文章可参考[37]-[50].事实上,可迹性,泛圈性,完全圈可扩性,哈密顿连通等这些之后提出的概念本质上都是对图的哈密顿问题的深层次的刻画. 最近若干年来,无爪图的概念也被从不同角度推广到了一些更大的图类,如:半无爪图,几乎无爪图,(K1,4;2)-图,DCT图等.其中,关于半无爪图的一些研究进展可参考[3],[26]-[28],关于几乎无爪图的可参考文献[29]-[32],关于(K1,4;2)-图的可参考[33]-[35].拟无爪图是滕延燕,尤海燕2004年基于几乎无爪图在[6]中提出来的,它也是对无爪图概念的一种推广,但它却包含在几乎无爪图类中,然而,很多在几乎无爪图中很难研究的东西在拟无爪图中却比较容易找到方法来研究.(V)独立集{x1,x2,…,xp}(∈)V(G)(p≥2),如果N(x1)∩N(x2)∩…N(xp)≠φ,那么若(V)u∈N(x1)∩N(x2)∩…N(xp),有N[u](∈)N[x1]∪N[x2]∪N[xp],则称u为{x1,x2,…,xp}的控制点.否则,称u为{x1,x2,…,xp}的非控制点.{x1,x2,…,xp}的控制点组成的集合称为{x1,x2,…,xp}的控制集,记为D(x1,x2,…,xp);{x1,x2,…,xp}的非控制点组成的集合称为{x1,x2,…,xp}的非控制集,记为(D)(x1,x2,…,xp).(V)独立集{x1,x2,…,xp}(∈)V(G)(p≥2),如果N(x1)∩N(x2)∩…N(xp)≠φ,那么D(x1,x2,…,xp)≠φ,且若(V)u∈D(x1,x2,…,xp),(V)v∈(D)(x1,x2,…,xp),有uv∈E(G),则称G为K1,p-扩展图.由定义不难知道K1,p1-free图一定是K1,p-扩展图.特别地,K1,3-free图一定是K1,2-扩展图.即易知K1,2-扩展图也是对无爪图的一种推广.这类图是我们在对图的结构进行深入研究的基础上提出来的. 本篇论文中,我们主要研究了拟无爪图的点泛圈性和不同连通条件下K1,2-扩展图的完全圈可扩性. 在第一章中,我们主要介绍了文章中所涉及的一些概念,术语符号和本文的研究背景以及已有的一些结果. 在第二章中,我们主要研究了拟无爪图的点泛圈性,证明了下面两个结果:定理2.2.3设G是连通的拟无爪图且δ(G)≥3,若G中同构于Z1的导出子图有性质φZ1(c,b1)或φz1(c,b2),则G是点泛圈的(其中Z1如图2.1中的图). 定理2.3.3设G是2-连通的拟无爪图且δ(G)≥3,若G中同构于Z2的导出子图有性质φZ2(a1,b1)和φZ2(a1,b2),则G是点泛圈的(其中Z2如图2.2中的图). 事实上,以上两个结果分别改进了H.J.Broersma,H.J.Veldman[36],MingchuLi[2]等人的相应结果. 在第三章中,我们探讨了不同条件下K1,2-扩展图的完全圈可扩性,改进了D.Oberly,D.Sumner[7],L.Clark[8]以及G.R.T.Hendry[9]的相应结果.得到了下面的三个定理:定理3.2.1设G是顶点数不小于3的连通的K1,2-扩展图,C为G中一r-圈(3≤r<|V(G)|).若G有一桥B,使得NC(B)中含局部连通的点,则G中含C的扩圈. 定理3.3.4顶点数不小于3的半局部连通的K1,2-扩展图是完全圈可扩的. 定理3.4.1顶点数不小于3的连通几乎局部连通的K1,2-扩展图G,若满足δ(G)≥3,则G是完全圈可扩的.且其中δ(G)的下界是最好可能的.
其他文献
本文主要研究无限维Hilbert空间上的K-框架.我们研究了基于K-框架性质上的算子刻画.得到了Bessel序列在算子K作用下为K-框架. K-框架在算子K*的作用下仍为K-框架的结论.同时
安森美半导体(ON Semiconductor)推出世界上分辨率最高的行间转移CCD器件KAI-47051图像传感器,为严格的工业检测和测绘应用中获得性能和能效的新水平。KAI-47051图像传感器分
图的哈密顿问题是图论中一个十分重要且又十分活跃的研究课题,每年都有大量的关于这一问题的学术论文。1857年,爱尔兰数学家哈密顿提出:“一个连通图有哈密顿圈的充要条件是什么
自从1998年底《国务院关于建立城镇职工基本医疗保险制度的决定》颁布以来,我国医疗保险体制改革经历了七个年度。在这七年中,我国的医疗保险制度改革取得了很大成绩,同时也面临
小组合作学习已经成为初中地理课堂教学中最为常见和实用的一种学习方式,但就教学实际来讲,小组合作学习存在着表面化、形式化的问题,未能取得良好的学习效果和教学效果。本
本文的主要工作分为两部分. 第一,本文基于二次模型及Perry提出的共轭性条件,导出共轭梯度法的主要参数β的两种新形式.它们可分别视为是对HS方法和PRP方法进行的修正.与经典的
常优5号是常熟市农科所用常01-11A与CR-27配组育成的三系杂交晚粳新组合,该组合具有米质优(在江苏省区试中米质达国标1级)、产量高、抗病性较强、制种产量高等特点,2010年分
在图像处理领域中,图像插值可以实现图像的缩放显示和提高图像的分辨率,在图像的清晰化处理和三维显示中具有十分重要的实用价值。本文给出了一种图像尺寸转换的新方法,该方
本文对山西农业机械化发展目标的估算和预测进行了研究。内容主要分以下几部分: 1.研究山西省农机化发展的意义,提出迫切需要提高农机改善策略,对于今后全省农机化的发展具有
对投资项目的评价和决策是企业经常要面对的问题。长期以来,现金流折现法和净现值法一直是应用最广泛的投资决策分析方法,但随着环境的变化,投资项目不确定性的增加,这些传统的决策方法受到挑战,人们开始探讨新的更符合现实的决策方法,期权决策法即利用期权理论对实物资产估价从而进行决策的方法应运而生,而期权决策法的最大难题在于实物期权的价值评估,本文就主要来研究投资项目决策中实物期权的价值评估,并结合实例说明如