2-连通[4,2]-图中的圈与高连通度图的完全圈可扩性

来源 :山东师范大学 | 被引量 : 0次 | 上传用户:xxf103000
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的哈密顿问题是图论中一个十分重要且又十分活跃的研究课题,每年都有大量的关于这一问题的学术论文。1857年,爱尔兰数学家哈密顿提出:“一个连通图有哈密顿圈的充要条件是什么?”这样一个问题。但是这个问题至今仍未能解决。后来人们发现它是一个NPC问题,于是降低要求间接研究该问题。与此同时,以Hamilton问题为出发点发展起了对图的圈性质的研究,这些性质主要包括Hamilton性、泛圈性、完全圈可扩性等。我们知道图的完全圈可扩性要比图的泛圈性更强,图的泛圈性要比图的哈密顿性更强,所以研究泛圈性和完全圈可扩性就研究了图的Hamilton性。关于哈密顿性的研究及最新进展可见参考文献[17]-[23]。关于泛圈性的研究及最新进展可见参考文献[24]-[34],关于完全圈可扩性的研究及最新进展可见参考文献[4]-[15]。对这些性质的研究主要集中在两方面,一方面是寻求这些圈性质的充分条件,另一方面是研究某些特殊图类的圈性质。 本文主要讨论了两种特殊图类中的圈性质的问题。一种图类是[s,t]-图,刘春房最早提出了[s,t]-图的概念并进行研究的。对[s,t]-图的研究有着深刻的应用价值,很典型的一个应用就是在计算机的网络配置上。另一种图类是高连通度图。这里的高连通度是指一个图的连通度相对图的阶是较高的。当一个图的连通度足够高时,这个图可以保证图的各种圈性质,那么随着图的连通度的降低,图的圈性质将发生什么变化呢?本文就此讨论了高连通度图的完全圈可扩性。为方便讨论,在第三章中提出了s-点连通图的概念,即连通度为κ(G)=|G|-s+1的图。在此基础上主要讨论了5-点连通图,6-点连通图的完全圈可扩性,即连通度分别为|G|-4和|G|-5的高连通度图的完全圈可扩性。根据所得结果提出了s-点连通图(κ(G)=|G|-s+1)在完全圈可扩性方面的一个猜想。在第三章最后给出例子说明定理及猜想中对图G的阶的限制是最好可能的。 本文的主要内容包括三章。在第一章中,我们主要介绍了文章中所涉及的一些概念、术语符号和本文的研究背景及已有的结果;在第二章中,我们讨论了2-连通[4,2]-图中的圈;在第三章中,我们讨论了高连通度图的完全圈可扩性并提出猜想。 我们得到的主要结果如下:定理2.1.1设G是2-连通[4,2]-图,C是G中满足|V(C)|<|V(G)|的任一圈,则或者G中有(|C|+1)-圈,或者G同构于K2,3,K1,1,3,F1,F2,F3,F4,F5。(其中F1,F2,F3,F4,F5如下图)推论3.1.1设G为4-点连通图且|G|≥7,则G是完全圈可扩的。定理3.1.1设G为5-点连通图且|G|≥9,则G是完全圈可扩的。定理3.1.1′设G满足κ(G)=|G|-4且|G|≥9,则G是完全圈可扩的定理3.1.2设G为6-点连通图且|G|≥11,则G是完全圈可扩的。定理3.1.2′设G满足κ(G)=|G|-5且|G|≥11,则G是完全圈可扩的。由上述定理提出下面的猜想猜想3.1.1设G为s-点连通图且|G|≥2s-1,则G是完全圈可扩的。 猜想3.1.1′设G满足κ(G)=|G|-s+1且|G|≥2s-1,则G是完全圈可扩的。 猜想3.1.1″设G为s-点连通图,若s≤[|G|+1/2],则G是完全圈可扩的。 猜想3.1.1"设图G满足κ(G)≥[|G+|+1/2],则G是完全圈可扩的。
其他文献
在环理论中,不同的矩阵有不同的作用,其中形式矩阵环占有非常重要的地位.在周毅强a class of formal matrix rings的论文中,主要介绍了由中心元s定义的R上的形式矩阵环Mn(R;s)的若
现代期权定价理论的革命始于1973年,在这一年,FischerBlack和MyronScholes发表了《期权定价和公司财务》一文,在一系列严格的假设条件下,通过严密的数学推导和论证,提出了后来被称
本文研究如下非线性脉冲微分系统的集合稳定性:脉冲泛函微分系统{x(t)=f(t,xt),t≥t0,t≠tκ,x(t+)=x(t)+Iκ(x(t)),t=tκ,κ=1,2,…,(1.2.1)xt0=(ψ)0,其中xt(θ)=x(t+θ),θ∈[-r,0],和脉
本论文主要研究如下在Eulerian坐标系中,描述一维可压缩流体流动的非线性偏微分方程的初边值问题{ρt+(ρu)x=0(ρu)t+(ρu2+p)x=μuxx(ρ(e+u2/2))t+(ρu(e+u2/)+pu)x=kθxx+
在小学语文课堂中,我们发现年级越高,学生发言的积极性越弱,低年级常常是想到了就说,高年级是想到了也不说,怕说得不好让人笑话。作为教师呢,低年级学生是只要说就捧场,高年
本文主要研究无限维Hilbert空间上的K-框架.我们研究了基于K-框架性质上的算子刻画.得到了Bessel序列在算子K作用下为K-框架. K-框架在算子K*的作用下仍为K-框架的结论.同时