【作者】 尹君；

【导师】 熊黎明；

【作者基本信息】 北京理工大学 ， 应用数学， 2016， 博士

【摘要】 哈密尔顿问题是结构图论中一个经典的研究课题,该问题与著名的四色问题存在着紧密联系.哈密尔顿问题在运筹学、通讯网络、社交网络、计算机科学、编码理论以及复杂性理论中都有着广泛应用.故而受到众多学者的青睐.本文主要研究图论中与哈密尔顿性质相关的一些问题,包括连通偶因子问题,哈密尔顿问题,最长圈问题以及哈密尔顿连通问题.全文共分为七章,下面分章节具体叙述本文的主要工作.第一章给出本论文的一些符号和术语,叙述图的哈密尔顿性相关问题的发展和国内外与此类问题相关的研究现状,并简单介绍本论文的结构,研究内容和主要结果.第二章利用禁用子图的概念来研究图的连通偶因子的存在条件.证明了顶点数至少为3,连通且局部连通的禁用K1,s+2的图包含一个连通的偶的[2,2s]-因子.第三章主要利用导出圈的性质来判断图的哈密尔顿性.证明了 3连通的线图,若它不含长度超过8的导出圈,则该线图是哈密尔顿图,这一结果可以推广到重爪图上.同时证明了对于3连通的无爪图,若它的每个长度至少为4的导出圈中至多含有8条非奇异边,则该无爪图是哈密尔顿图;若它每个长度至少为4的导出圈中至多含有11条非奇异边,则要么它是哈密尔顿图,要么它的闭包是经过收缩可变为Petersen图的那些图的线图.任意2连通的无爪图,若它最长的导出圈的长度不小于n-2,那么该图是哈密尔顿图.上述这些结果都是最好可能的.第四章研究了最小度δ ≥ 3的n阶无爪图,若它含有长度超过4n-2δ-4/δ+2的导出圈,则它是哈密尔顿图.当δ ∈ {3,4}时,上述下界是最好可能的.当δ ≥ 5时,虽然我们不知道它是不是最好可能的,但是有例子表明:δ ≥ 5时,这一结果最好可能的界不会小于4n-4δ-4/δ+2.第五章证明了下面的结果:设G是顶点数为n连通度为κ(G)的图,且有κ(G)≥k≥ 2 与n≥2 + 1,则图G的每一个最长圈包括度数至少为d的所有顶点,这里d = max {[n/2],n-3k+2}.结合独立数的条件,获得了如下结论:设G是阶数为n,独立数为α的k连通图,则图G的每一个最长圈包括度数超过d0的所有顶点,这里d0=(α-k)n-kα+k2 +α2-2α/α.第六章介绍图G的加强闭包GM的定义及性质,并利用这一概念,证明了,如果图G满足一些附加条件时,G是哈密尔顿连通的当且仅当其闭包cl(G)是哈密尔顿连通的.具体结果为:任意一个2连通的无爪图G,其最小度δ(G)≥3,如果G有一个无漏斗的加强闭包GM,那么G是哈密尔顿连通的当且仅当cl(G)是哈密尔顿连通的.第七章总结本论文所做的主要工作,对今后的研究工作做一展望.更多还原

【Abstract】 The hamiltonian problem is a classical topic in structural graph theory,which is closely related to Four Color Problem.Hamilton problem has been widely used in operational research,communication networks,social networks,computer science,coding theory and complexity theory.Hence lots of graph scholars are dedicated to this topic.In this thesis,we study some problems related to hamiltonian properties of graphs,including connected even factors,hamiltonian cycle,the longest cycle problem,Hamilton-connected problems.The full paper contains seven chapters.In the following,let me explain explicitly what I have done.In Chapter 1,we list some symbols and terminologies,which will be used throughout this thesis.Then,a general survey of this thesis as well as preliminaries on hamiltonian properties,and the development of hamiltonian problems at home and abroad are given.We also introduce the structure of this thesis,including the research content and main results.In Chapter 2,we introduce the concept of H-free graphs,and study the existence con-ditions of connected even factors.It is proved that if G is a connected,locally connected K1,s+2-free graph of order p>3,then G has a connected even[2,2s]-factor.In Chapter 3,we give sufficient conditions to judge the hamiltonian property by using induced cycle.It is proved that every 3-connected line graph such that every induced cycle is of length at most 8 is hamiltonian,and this result can be extended into o-heavy graph.It is shown that every 3-connected claw-free graph such that every induced cycle of length at least 4 has at most 8 edges contained in a triangle is hamiltonian.We also show that every 3-connected claw-free graph whose every induced cycle of length at least 4 has at most 11 edges contained in a triangle is hamiltonian or its closure is line graph of the graph contractible to the Petersen graph.Every 2-connected claw-free graph of longest induced cycle with length at least n-2 is hamiltonian.These results are all best possible.In Chapter 4,we obtain the following:let G be a claw-free graph with n vertices and minimum degree δ(G)≥3.If G has an induced cycle of length more than 4n-2δ(G)-4/δ(G)-2,then G is hamiltonian.The result is best possible for δ(G)∈ {3,4}.Although we do not know whether it is also best possible for δ ≥ 5,some example shows the best possible bound may not less than 4n-2δ-4/δ+2.In Chapter 5,we prove that:let G be a graph of connectivity κ(G)≥ k ≥ 2 and of order n ≥ 2k + 1,then every longest cycle of G contains all vertices of degree at least d = max {[n/2],n-3k + 2}.Using an additional condition of independent number,we have that:let G be a k-connected graph of order n and of independent number α,then every longest cycle of G contains all vertices of degree more than d0=(α-k)n-kα+k2+α2-2α/α.In Chapter 6,we introduce the concept and property of SM-closure of G.In what additional conditions may guarantee that "G is Hamilton-connected if and only if the closure cl(G)of G is Hamilton-connected"?The result is that if G is a 2-connected claw-free graph with minimum degree at least 3 such that its SM-closure GM is hourglass-free,then G is hamilton-connected if and only if the closure cl(G)of G is hamilton-connected.In Chapter 7,we give a conclusion.In this chapter,the main contribution of this thesis is summarized and the expectation is made.更多还原