图中强路圈性质的若干充分条件

来源 :山东师范大学 | 被引量 : 11次 | 上传用户:jinyu1016
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的路和圈问题是图论中—个十分重要而且活跃的研究课题,有大量的实际问题可以归结为图的路和圈问题.图论中三大著名难题之一的Hamilton问题本质上也是图的路和圈问题.国内外许多学者对此问题作了大量的研究工作.这方面的研究成果和进展可参见文献[38]—[42].其中度条件和邻域并条件成为研究路和圈问题的重要途径,在这方面取得了很多优秀的成果.经过几十年的发展,图的路圈性质所涉及的内容日益丰富和具体.路的方面包括图的Hamilton路(可迹性):齐次可迹性,最长路,Hamilton连通,泛连通,路可扩等等;圈的方面包括图的Hamilton圈,最长圈,(点)泛圈,完全圈可扩,点不交的圈,圈覆盖等等. 由于直接研究—般图的Hamilton问题往往比较困难,于是人们转而研究不含有某些禁用子图的图类.继Beineke1970年发表的关于线图性质的文章[17]之后,人们开始关注包含着线图的无爪图.70年代末80年代初,是研究无爪图的一个非常活跃的时期.关于无爪图方面的部分优秀成果可参考[1]—[3],[19]—[31].另外,无爪图的概念也被从不同角度推广到了更大的图类,半无爪图,几乎无爪图,(K1,4;2)—图等.2005年,刘春房在[4]中定义了一种新的图类—[s,t)—图,即任意s个点之间至少含有t条边.而我在这类[s,t]—图的基础上提出了强—[s,t]图,即任意s个点之间至少含有t条独立边,这类图的特点是其边的分布比较均匀,因而在交通网络,通信系统,计算机的网络配置等方面有着很典型的应用. 本文就是研究强—[s,t]图和一般图中与度有关的强路圈性质. 在第一章中,我们主要介绍文章中所涉及的一些概念和术语符号,以及本文的研究背景和已有的一些结果. 在第二章中,我们主要研究了强—[s,t]图在不同条件下的强路圈性质,得到下面的结果: 定理2.1.4设G是n(n≥6)阶强—[4,2]图,则G是泛圈的. 定理2.1.5设G是n(n≥7)阶强—[4,2]图,则G是完全圈可扩的. 定理2.1.6设G是n(n≥8)阶强—[4,2]图,则G是路可扩的, 定理2.2.4设G是n(n≥8)阶连通强—[5,2]图,则C含有Hamilton路. 定理2.2.5设G是δ(G)≥3的连通,局部连通的强—[5,2]图,则G是完全圈可扩的或者同构于图F. 推论2.2.6设G是δ(G)≥3的n(n>8)阶连通,局部连通的强—[5,2]图,则G是完全圈可扩的. 定理2.3.3设G是n(n≥3m-1)阶强—[2m,m]图,则G含有Hamilton路. 定理2.3.4设G是n(n≥3m)阶强—[2m,m]图,则G含有Hamilton圈. 在第三章中,讨论了图中在与度有关的条件下关于圈的几个结果: 定理3.8设G的阶n≥3,如果G中任意一对不相邻的顶点u,v满足d(u)+d(u)≥n+k,则G中任意—个满足n/k+2<|C|<n的圈C是可扩的. 推论3.9设G的阶n≥3,如果G中任意一对不相邻的顶点u,v满足d(u)+d(v)≥3/2n—2,则G是完全圈可扩的, 定理3.10设G的阶n≥3,如果G中任意一对d(u,v)=2的顶点u,v,满足d(u)+d(v)≥n+1,则存在—个顶点x∈{u,v),过x有各种长度的圈. 在第四章中,讨论了图中在与度有关的条件下关于路的几个结果: 定理4.3设G的阶n≥3,如果G中任意一对不同的顶点u,v满足d(u)+d(v)≥n+1,则G是路可扩的. 定理4.4设G的阶n≥3,如果G中任意一对不相邻的顶点u,v满足d(u)+d(v)≥n+1,则C中任意一条满足n/3+1<|P|<n的路P可扩的.
其他文献
时滞微分方程是现代应用数学的一个重要分支,作为数学模型广泛应用于力学,控制论,生态学,管理学及流行病学等许多领域中.关于时滞微分方程理论已有大量研究,并取得了优秀的成果,本文
在新课程改革的背景下,有效提问在初中物理中起着重要的作用,是物理教学的核心.在物理课堂教学中的有效提问,可以让学生根据已知信息,将复杂和困难的问题转变成简单的问题,使
对于供应链成本来说,生产、库存、运输过程都是需要相应的成本的,所以供应链管理者对于生产、库存、运输的管理尤其重视。正因如此,加强供应链中的生产成本、管理成本和运输成本也变得尤其重要,但以往的文献主要考虑的是生产与库存或是库存与运输两阶段的联合优化。文章前半部分是在随机的需求背景下来考虑生产-库存-运输联合优化的问题,文章后半部分研究的是变质性物品的库存费用。本文的主要研究工作如下:(1)研究生产-
1990年,Hilger引入了时间测度上动力方程这个概念,并迅速延伸为一个重要的研究领域,这个新理论统一了连续和离散计算的方法,并给出了连续和离散两个领域中均适用的抽象概念.时间测
在本次金融危机中,发现信用评级机构存在的问题是一大收获,投资者开始怀疑信用评级机构评级的准确性。国际证监会组织修改了外部信用评级机构的行为准则,加强了对评级过程质
切换系统是一类混杂动态系统,由一族连续时间或者离散时间的子系统所组成,并且在这些子系统之间有一个切换规则,协调控制着整个系统的运行。切换系统作为一类特殊的混杂系统,可为
设Kv是一个v个点的完全图,G为Kv的一个不含孤立点的简单子图.Kv的一个G-设计,常记为(v,G,1)- GD,是指一个二元组(X,B),其中X为Kv的顶点集,B是Kv的一些子图(亦称为区组)构成的集合,使得
现代教育中,不少中学生都反映数学是最令其头疼的课程,但作为一门讲究思维逻辑性的课程,不仅要掌握了公式和应用规律,更要探究其中的乐趣,也许数学并没有那么难学,之所以造成
随着社会经济和科技的发展,互联网络与人们的工作、日常生活等方面的关系越来越密切,自然,网络的可靠性和容错性倍受人们的关注.研究网络的可靠性和容错性是社会发展的必然趋势,是
艺术设计专业的实验教学有别于综合性大学或工科院校的实验教学. 构建艺术设计专业创新人才培养的实验教学体系的关键,是从“实验”概念、培养目标上对实验教学要有新的认识,并