论文部分内容阅读
图论是数学的一个分支.它以图为研究对象.通常通过研究一个图存在什么样的子图以及这个图具有什么样的性质来了解这个图的结构.本文主要研究图中点不交的星图,小阶完全图,圈以及边临界图的平均度和哈密尔顿性. 如果一个图不包含同构于K1,r的导出子图,则称这个图是无K1,r的.特别地,当r=3时,称这样的图为无爪图.在2008年,Fujita提出了关于无K1,r图的一个猜想:设k≥2,r≥3和t≥2均为整数,对任意阶为n的无K1,r图G,如果n≥(k-1)(t(r-1)+1)+1并且δ(G)≥t,则G包含k个点不交的K1,t.关于这个猜想,Fujita验证了t=2和r=t=3的情况,并且他还证明了当n≥(t+1)(k-1)(t(r-1)+1)+1时猜想成立.在第二章中,证明了这个猜想在r≥4,t=3以及r≥2t-1,t≥3的情况下是成立的,并且当n≥(k-1)(t(r-1)+1+(t-1)(t-2))+1时猜想也是成立的.另外,构造了一个阶为10k-10,δ(G)=4的图G使得它不包含k个点不交的K1,4,因此,当r=3,t=4时G是Fujita猜想的一个反例. 如果一个图的任意两点都相邻,则称这样的图为完全图,并将阶为n的完全图记为Kn.Wang于1998年证明了如果图G是阶至少为3s的无爪图并且σ2(G)≥3s+1,其中s是正整数,那么除了一些特例,图G包含s个点不交的K3.在第三章中,主要研究无爪图包含点不交的K3和K4的问题,并证明了对任意的正整数s和k以及阶为n的无爪图G,如果n≥3s+4(k-s)并且对任意不相邻的两点x和y都有d(x)+d(y)≥n-2s+2k+1,那么G包含s个点不交的K3和k-s个点不交的K4使得它们互相之间也是点不交的. 在2015年,Wang研究了局部度条件下图中包含特定的点不交圈的问题,并证明了对任意正整数k,阶为n≥3的图G,以及V(G)的大小至少为3k的子集W,如果对任意x∈W都有d(x)≥2n/3,则G包含k个点不交的圈并且每个圈至少包含W中的三个点.在第四章中,考虑了关于二部图的类似问题,并证明了对任意正整数k和阶为2n的均衡二部图G=(V1,V2;E)以及V1的一个子集W,其中|W|≥2k,如果任意两点x∈W和y∈V2都有d(x)+d(y)≥n+k,则G包含k个点不交的圈使得每个圈至少包含W中两个点. 给定图G和映射φ:E(G)→{1,2,…,k},如果对G中任意两条相邻的边e和f都有φ(e)≠φ(f),则称φ是图G的一个边-k-染色,并称{1,2,…,k}是φ的颜色集.用Ck(G)来表示G的所有边-k-染色的集合.另外,边色数x(G)是使得Ck(G)非空的最小非负整数k.并将图的最大度和平均度分别记为△和d(G).如果)x(G)=△+1并且对G的任何真子图H都有x(H)≤△,那么称图G是边-△-临界图.1968年,Vizing提出了边临界图的平均度猜想,即任意阶为n的边-△-临界图G都有(d)(G)≥△-1+3/n.在2007年,Woodall证明了边-△-临界图G的平均度至少为2/3(△+1).在第五章中,给出了边-△-临界图的一个新结构并证明了如果G是边-△-临界图,那么(d)(G)≥{0.69241△-0.15658若△≥66;0.69392△-0.20642若△=65;0.68706△+0.19815若56≤△≤64.当△≥56时,这个结果改进了Woodall的结果.另外,关于边-△-临界图是否包含哈密尔顿圈的问题,Chen,Chen和Zhao于2017年证明了最大度△≥3|G|/4的边-△-临界图G是哈密尔顿的.当n>144时改进了这一结果,并且证明了对任意的边-△-临界图G,如果△≥2|G|/3+12,那么G是哈密尔顿的.