k连通图中的k可收缩边

来源 :广西师范大学 | 被引量 : 0次 | 上传用户:yanhsy
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
如果将k连通图G中的一条边收缩之后所得到的图仍然是k连通图,则称这条边为G的k可收缩边,简称可收缩边.否则称为不可收缩边.如果k连通图中存在可收缩边,则可使用归纳法去证明k连通图的某些性质,因此研究图的可收缩边是很有意义的.在k连通图中,若边 xy在一个三角形xyz上,d(x)=k,易见xy不是可收缩边,图中这样的不可收缩边称为平凡的不可收缩边 1961年,Tutte在([1])中证明了阶至少是5的3连通图有可收缩.边于k≥4,Thomassen在([2])中证明了存在无限多个k连通k正则图不含k可收缩边.为得到k连通图中存在可收缩边的条件,人人们引进了收缩临界k连通图的概念.一个不是完全图的k连通图称为收缩临界k连通图,如果它的每一条边都不可收缩容易看出收缩临界k连通图的每一个性质的否定都是k连通图中存在可收缩边的充分条件不难证明没有收缩临界1或2连通图,山Tutte上述证明的结论知也无收缩临界3连通图.收缩临界4连通图已被Fontet([3])与Mortonov([4])独立地完全刻而:若G是一个没有可收缩边的4连通图,则G或者是一个圈的平方,或者是一个圈4连通3正则图的线图.刻而收缩临界5连通图要比刻而收缩临界4连通图凼难得多,迄今还没有满意的结果,更不用说刻而一般的收缩临界k连通图了.当前研究k连通图的可收缩边的一个重要内容是研究收缩临界k连通图的性质,由此给出k连通图中存在可收缩边的一些充分条件: 1981年,Thomassen在([12])中证明了如下定理: 定理A 设G是一个不含可收缩边的k连通图,则G一定含有三角形K3 即,若k连通图G不含三角形,则G中存在k可收缩边,Egaw a 等在([5])中计算了无三角形的k连通图中可收缩边的条数,他证叫了: 定理B 每一个无三角形的k连通图G,至少有min{|V(G)|+2/3K2-3k,|E(G)|}条可收缩边 定理B说明了无三角形的k连通图有相当多的可收缩边.用无三角形的条件来限制收缩边存在的条件似乎太强了. Egowo在([6])中研究了k连通图中含有可收缩边的最小度条件,证明了如下定理: 定理c 设k≥2是一个整数,设G是一个k连通图,6(G)≥[5K/4],则G有一条k可收缩边.除非2≤k≤3,上_GH构于Kowarabayashid ([7])中证明了: 若一个图G没有了图同构于图H,我们称G是H-free图.K-4表示从K4=中移去一条边后所得到的图,Kowar abaya shi 在([7])中证明了: 定理D([7]) 设k≥3为奇数,若G为不含K的k连通图,则G中有可收缩边 李向軍等对K free k连通图作了进一步的研究,在([8])中得到了K-4 free k连通图中可收缩边条数的一个下界: 定理E ([8]) k≥5为奇数,G为K free k连通图,则G有k+1条可收缩边 三角形在可收缩边的研究中扮演了一个重要角色 MoJJer在(19中证明了收缩临界k连通图中含有很多三角形,他得到了: 定理F ([9]) 设G是一个收缩临界k连通图,则G 中至少有|V(G)|/3个三角形 而最近Kriese肌在([10])中改进了M ader 的结果,他证明了收缩临界k连通图中至少有()个三角形 一个boruustie 是指一个山两个恰有一个公共顶点的三角形构成的图形,最近Ando等人在([11])中得到如下结果: 定理G 设k≥4是一个整数,若一个k连通图G中没有可收缩边,则G中含有boutie 即,若一个k(k≥4)连通图G中不含boutie,则G中含有可收缩边。 通过仔细考察bcnutie free k连通图,我们在本文第一章中得到如下定理: 定理1 设G是无boutie 作为了图,也无H图作为导出了图的k连通图,则G中至少有k条可收缩边(k ≥4) (图H=kKl+K2-{uy,vx)+[xy]其中K2=uv,x,y∈(kK1),即H中有一个圈,该圈恰有一条边在k 2个三角形上) 我们给出了一个例了,说明定理中的k这个下界是一个较好的下界 定理2 设G是无boutie,也无(k-2)K1+K2的k连通图,则G中至少有2k条可收缩边(k≥4) 本文第二章讨论极小k连通图中含有可收缩边的禁用了图条件设G是k(>2)连通图,若对任意一条边e∈E(G)都有G e不再K连通,则称G为一个极小k连通图.对k连通图G,如果G不是极小k连通图,我们可以在保持k连通性的前提下,通过去掉图G中的一些边,直到所得到的图是极小k连通的,因此每个k连通图中都有一个极小k连通了图。显然如果G是H free,则它的任意一个了图也是H-free的,另一方面,如果G的k连通了图含有可收缩边e,那么e也是G的可收缩边。 因此讨论极小k连通图中存在可收缩边的条什是有意义的。 Ando等在([12])中得到了下面的结论: 定理H 设G是一个极小k (k≥5)连通图,不含K1+C4, 任意一个k度点x∈V(G),E(x)中有一条边不含在任们三角形中,则G中有一条k可收缩边 对极小k连通图中的可收缩边,齐恩风等在([13])中证明了,在k≥8时,若极小k连通图G中不含P=K1+2p3,如果G中任-k度点x,都存在与x关联的不在三角形中的边,那么G中有k可收缩边 考察K1+G4,不难发现,K1+C4b即为 ps+2K1我们在第二章中得到了下面的结论: 定理3 若极小k (K≥5)连通图 G中不含Ps+3Ki,G中任意一个k度点x∈V(G),E(x)中有一条边不含在任任何三角形中,则G中有一条k可收缩边 我们构造了一个5正则5连通图,含有K1+C4,但不含p3+3Ki每个5度点关联一条不在三角形上的边,符合定理3的条件,但不满足定理H的条件,而容易验证,图G中有可收缩边.从这个例了可以看出,用定理3中的条件来限制可收缩边的存在比用定理H中的条件要好些山定理3,我们自然想进一步推广定理3,我们得到了下面的结论: 定理4 设G是不含P3+tK1 的极小k连通图,G中任意一个k度点x∈V(G),E(x)中有一条不在三角形中的边,则与k≥4t-1时,G有可收缩边(t≥4)。
其他文献
非自伴算子代数是算子代数理论的重要分支,而自反算子代数又是研究非自伴算子代数的主要内容。自从60年代J.Ringrose开始研究套代数以来,人们对套代数、交换子空间格代数和完全
新课程改革对中学高年级教师提出了新的要求,高中教学中教师是教学的主导,主导者的转变能促进作为学习主体的学生更好的转变。为实现高中历史新课改的目标和要求,历史教师角
请下载后查看,本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.
期刊
图像的分辨率决定了描述图像细节的丰富程度,因此对于现有图像,如何提高它的分辨率,是当前图像处理技术研究的热点。为了不增加硬件成本,在现有图像的基础上提高图像分辨率,
延迟随机微分方程(SDDE)的应用一直十分广泛,由于解析解难以求得,所以数值解成为人们研究的重心。因此,如何构造一个具有强收敛性的数值解成为难点和重点。关于随机微分方程的数
在对实际控制系统建模时,由于不可避免地存在着测量误差、各种干扰及未建模动态等,导致系统模型与实际问题之间存在着误差,一般称这些误差为系统中的不确定性。另外,很多系统中的
RISI首席经济顾问Rod Young报道(摘要):2月25日中国政府发布从2013年2月6日开始对从巴西、加拿大、和美国进口的溶解浆实施反倾销调查。该调查延续一年, Rod Young, Chief E
本文对半序集上的一类多值增算子不动点的存在性进行了研究,当算子不具有紧性或者连续性时,在一定的假设条件下,证明了一类增算子极大不动点和极小不动点的存在性;另外,在拟偏好意
期刊
文艺新风习近平总书记在文艺工作座谈会上的讲话引发了全社会的高度关注和广泛讨论,舆论普遍认为此次讲话对今后文艺工作的健康发展和文化领域的改革创新具有深刻影响和深远