图的路圈性质及连通性的研究

来源 :山东师范大学 | 被引量 : 0次 | 上传用户:wyh
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图论是现代数学的重要分支之一,图的路、圈问题又是图论中一个十分重要而且活跃的研究课题,大量的实际问题可以归结为路和圈的问题.事实上,图论中三大著名难题之一的Hamilton问题本质上也是图的路和圈问题.这方面的研究成果和进展可参见文献.由于直接研究一般图的Hamilton问题往往比较困难,于是人们转而研究不含有某些禁用子图的图类,如无爪图.继Beineke1970年发表的关于线图性质的文章之后,人们开始关注包含着线图的无爪图.70年代末80年代初,是研究无爪图的一个非常活跃的时期.关于无爪图方面的部分优秀成果可参考.  如果图G中任意s个顶点之间至少存在t条边,则称 G是[s,t]-图.这一概念是刘春房,王江鲁2005年在中给出的.由于”a(G)2),则G或者含有Hamilton路或者同构于Kk+2VGk.  由这两个结果可以分别推得Chvatal-Erdis和Bondy用点独立数a(G)和连通度k:(G)给出的下述经典结果:  (a)(Chvatal-Erdos and Bondy)设图G的阶n>3,如果a(G)3,如果a(G)3,如果a(G)2),则 G或者是HamHton连通的或者同构于KkVGk.  推论2.1.1设G是n(>3)阶,k-连通[k+1,2]—图且|G|>2 k+1,则G是Hamilton连通的.  推论2.1.2设G是n(>3)阶,k+1,k-连通[k;+1,2]图,则G为Hamilton连通.  推论2.1.3设 G是n(23)阶,a(G)< k—1,则 G为H a m说on连通.  定理2.1.2若图G是6> k+1,k—连通[k+2,3]—图(fc>2),则 G或者是Hampton连通的或者同构于Kk+1VGk+i.  推论2.1.4设 G是n(23)阶,6> k+1,k—连通[k+2,3]图且|G|>2k+3,则 G是Hampton连通的.  推论2.1.5设G是n(>3)阶,6>&+2,连通[k+2,3]—图,则G为Ham沿on连通.  在第三章中,讨论了在|NC(B)|> k(|Np(B)|>幻的条件下[s,t]—图的Hampton的路圈性质,得到下面的结果:  定理3.1.1设图G是[k+3,2]—图(k>2)且不含Hamilton路,P是 G的一条最长路,如果对G-V(P)的任一分支B有|Np(B)|则G同构于VGk.  推论3.1.1若图G是;fc-连通[k+3,2]-图,则 G或者含有Ham说on路或者同构于Kk+2VGk.  定理3.1.2设图G是6>k+1,[k+4,3]-图>2且不含Hamilton路,P是G的一条最长路,如果对G-V(P)的任一分支B有|Np(B)|>k,则 G同构于Kk+3VGk+1.  推论3.1.2间若 G是6>k+1的k-连通[k+4,3]—图,则G有Ham沿on路或G同构于Kk+3VGk+i.  定理3.1.3设图G是[k+2,2]—图(k>2)且不含Hamilton圈,C是G的一条最长圈,如果对G—V(C)的任一分支B有|NC(B)|>&,则G或者同构于Petersen图或者同构于Kk+1VGk.  推论3.1.3间若图G是I连通[&+2,2]-图,则 G或者含有Ham沿on圈或者同构于Petersen图或者同构于Kk+iVGk.  定理3.1.4设图G是[k+1,2]—图(k>2)且不是Hamilton连通的,P是G的一条最长路,如果对G—V(P)的任一分支B有|Np(B)|则G同构于KkVGk.  定理3.1.5设图 G是6>k+1,[k+2,3]—图(k>2)且不是Hamilton连通的,P是G的一条最长路,如果对G—V(P)的任一分支B有|Np(B)|则G同构于Kk+iVGk+i.  定理3.2.1设图G是6(G)>3,[4,2]—图且不含Hamilton圈,C是G的一条最长圈如果对G—V(C)的任一分支B有|NC(B)|>1,则 G有2-因子.  推论3.2.1[叫设图G是连通[4,2]—图,若6(G)>3,则 G有2-因子.  定理3.2.2设图G的阶为n(n>5),是[k+2,1]—图(k>2)且不含Hamilton圈,C是G的一条最长圈如果对G—V(C)的任一分支B有|NC(B)|则G有2-因子.  推论3.2.2[叫设图G是n(n>5)阶k-连通[k+2,1]—图,则G有2-因子.  在第四章中,涉及的是[s,t]-图的Dominating性质,得到下面的结果:  定理4.1.1若图G是k—连通[&+3,3]-图(&>2),则G含有Dominating圈.  定理4.2.1若图G是k—连通[k+4,3]-图(k>2),则G含有Dominating路.
其他文献
本篇文章主要考虑的是如何最大化全部折现分红和最终的固定资产P的和。其中最终固定资产P表示保险公司在破产时所拥有的固定的可折算成资金的资产。本篇文章中,保险公司的资金
序集抽样方法是上世纪50年代McIntyre在寻求能较好估计牧场草的产量时提出来的.它是假定在一个无穷总体中,对每一个体进行准确测量的费用很高或时间很长,而对他们或其相关的量
董事长作为股东利益代表行使决策权,总经理作为公司经营者行使执行权,两者本应在《公司法》和公司章程等法律或制度构筑好的权力框架下各司其职、各负其责,相互合作、相互支
分数阶微积分在众多领域有着广泛的应用,而用分数阶扩散方程描述粒子的反常扩散现象则是分数阶微积分的一个典型应用。因分数阶微积分的历史依赖性和非局部性质,增加了分数阶微
相关特性和线性复杂度是影响伪随机序列在通讯和密码系统中应用的两个决定性因素.为了有效地抵抗互相关攻击,在流密码系统中的密钥流序列应具有低相关性质;另一方面,在CDMA通信系
分子动力学程序是用来模拟生物分子的行为并研究它们的结构和功能。当问题的规模固定时,分子动力学程序需要达到非常好的可扩展性。NAMD是一个可扩展的分子动力学软件,在很多的
本文的内容主要是围绕线性模型参数估计精度的评判展开的。在参数估计领域,评价一个参数估计方法的好坏,我们常常使用的是损失函数这样一个数学统计工具。在线性模型领域,长期以