半无爪图的Hamilton性质

来源 :山东师范大学 | 被引量 : 0次 | 上传用户:daviid
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
Hamilton问题是图论研究的基本问题之一,1857年爱尔兰数学家Hamilton提出这样一个问题:“一个连通图是Hamilton图的充要条件是什么?”这个问题至今尚未解决,后来人们发现它是一个NPC问题,于是对它降低要求,间接研究该问题.一种思路是研究Hamilton图的充分条件,另一种思路是研究特殊的图类,如:正则图,t一坚韧图,无爪图,半无爪图等. 关于无爪图的Hamilton性质,近几十年来,许多数学学者致力于它的研究,并且得到了很多优美的结论.Ainouche在文献[2]中首先引进半无爪图的定义,半无爪图是包含无爪图的更大的图类,Ainouche在文献[2]中将无爪图的一些结果,特别是关于Hamilton性质的,推广到半无爪图.本文将无爪图的另外的一些结果推广至半无爪图时也成立.这样,这些性质可以应用到更大的图类上. 本文仅讨论有限、无向、简单图,设G是一个图,V(G)和E(G)分别表示G的顶点集和边集.对任意v∈V(G),N(v)表示点v在G中的邻点集,N[v]=N(v)∪{v}.设G是连通图,对于u,v∈V(G),d(u,v)表示u,v之间的最短路长,称为u,v的距离.若G中无同构与K13的导出子图,则称G是无爪图.如果任意x,y∈V(G),d(x,y)=2,都存在u∈N(x)∩N(y),使得N(u)()N(x)∪N(y),则称G是半无爪图.显然,半无爪图是包含无爪图的更大的图类. 在第一章预备知识中介绍了半无爪图Hamilton性质的研究现状及本文涉及到的图论的一些基本概念、基本知识和使用的有关术语、符号. 关于2-连通无爪图,有以下结果: 定理[3]若G是2-连通的无爪图,其阶为n,则当n≤3δ+2时,G是Hamilton图. 在第二章2-连通半无爪图的Hamilton性质中把这个结果推广至半无爪图: 定理若G是2-连通的半无爪图,其阶为n,则当n≤3δ+2时,G是Hamilton图. 关于3-连通无爪图,有以下结果: 定理[4]若G是3-连通的无爪图,其阶为n,则当n≤5δ-5时,G是Hamilton图. 在第三章3-连通半无爪图的Hamilton性质中将这个结果推广至半无爪图类,并且把n的值提高到5δ-4,证明了半无爪图的以下结果: 定理若G是3-连通的半无爪图,其阶为n,则当n≤5δ-4时,G是Hamilton图. 关于k-连通半无爪图有以下结果: 定理乜]若G是k-连通的半无爪图(k≥2),如果对于G中任意基数为k+1的独立集X,都有∑v∈Xd(v)≥n-k,则G是Hamilton图. 在第四章k-连通半无爪图的Hamilton性质中证明以下结论,它减弱了以上定理的条件: 定理若G是k-连通的半无爪图(k≥2),如果对于G2中任意基数为k+1的独立集X,都有∑v∈Xd(v)≥n-k,则G是Hamilton图. 在第五章图的控制圈的一个下界中得到以下结论,它在特定的条件下推广了田丰在[19]中的结果: 定理若G是2-连通的非Hamilton图,含有一个控制圈C,令R:V(G)-V(C),如果存在v∈V(C),使dR(v)≥2,则G包含的控制圈的长至少为2σ-2.
其他文献
约束矩阼方程问题是指在满足一定条件的矩阵集合中求矩阼方程的解。不同的约束条件,不同的矩阵方程类型就导致了不同的约束矩阼方程问题。约束矩阵方程问题在结构设计,参数识别
安放骨灰的由来 贺龙一案完全是林彪、“四人帮”制造的一个大冤案。“9·13”林彪叛国爆炸之后,1972年1月,毛主席参加陈毅元帅追悼会接见张茜时说,看来对贺龙的问题也要重
本论文研究的内容包括两个部分。首先,介绍了图的因子理论中关于(g,f)-k-覆盖图和(g,f)-k-消去图的研究现状,并分别得到了当g≤f时一个二部图G=(X,Y)是(g,f)-2-覆盖图和(g,f)-3-覆盖
请下载后查看,本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.
期刊
这是几则关于交纳党费的小故事,读来颇有感触。老一辈共产党人,怀着神圣的阶级感情,无论生活多么艰苦,环境多么恶劣,时刻不忘一个共产党人崇高的信念和责任。与此相反,现在一
现阶段,教学管理工作的主要对象是人,所以,在教学管理工作开展过程中,管理工作者应该注意将以人为本的理念融入工作中,促使教学管理工作水平和质量得到显著提升.本文围绕教学
随着现代社会的不断发展,石油在国家经济发展和国家安全中的地位日益凸显。中国作为世界第一大石油净进口国,石油关乎中国社会安定、经济发展、政治稳定和国家安全。探索石油股
期刊
《英语课程标准》强调教学过程是师生交往、共同发展的互动过程.在教学中我们要“以人为本”,遵循“以学生发展为目标”展开教学.但是,在小学高年级英语教学中,有部分学生对
二〇一四年六月二十八日,由中国文联、中国书协、中华海外联谊会教科文卫体委员会、《科技日报》主办,中国书协中直机关分会、和平世界书画院承办的张飙撰并书《甲午一百二十