论文部分内容阅读
如果将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)。