k连通图中的k可收缩边

论文摘要

如果将k连通图G中的一条边收缩之后所得到的图仍然是k连通图，则称这条边为G的k可收缩边，简称可收缩边。否则称为不可收缩边。如果k连通图中存在可收缩边，则可使用归纳法去证明k连通图的某些性质，因此研究图的可收缩边是很有意义的。在k连通图中。若边xy在一个三角形xyz上，且d（z）=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连通图已被Fonet（[3]）与Martinov（[4]）独立地完全刻画：若G是一个没有可收缩边的4连通图，则G或者是一个圈的平方，或者是一个圈4连通3正则图的线图。刻画收缩临界5连通图要比刻画收缩临界4连通图困难得多，迄今还没有满意的结果，更不用说刻画一般的收缩临界k连通图了。当前研究k连通图的可收缩边的一个重要内容是研究收缩临界k连通图的性质，由此给出k连通图中存在可收缩边的一些充分条件。1981年，Thomassen在（[2]）中证明了如下定理：定理A设G是一个不含可收缩边的k连通图，则G一定含有三角形K3。即，若k连通图G不含三角形，则G中存在k可收缩边，Egawa等在（[5]）中计算了无三角形的k连通图中可收缩边的条数，他证明了：定理B每一个无三角形的k连通图G，至少有min{|V（G）|+2／3k2-3k，|E（G）|}条可收缩边。定理B说明无三角形的k连通图有相当多的可收缩边。用无三角形的条件来限制收缩边存在的条件似乎太强了。Egawa在（[6]）中研究了k连通图中含有可收缩边的最小度条件，证明了如下定理：定理C设k≥2是一个整数，设G是一个k连通图，δ=（G）≥[5k／4]，则G有一条k可收缩边。除非2≤k≤3，且G同构于Kk+1。若一个图G没有子图同构于图H，我们称G是H-free图。K4-表示从K4中移去一条边后所得到的图，Kawarabayashi在（[7]）中证明了：定理D（[7]）设k≥3为奇数，若G为不含K4-的k连通图，则G中有可收缩边。李向军等对K4-free k连通图作了进一步的研究，在（[8]）中得到了K4-free k连通图中可收缩边条数的一个下界：定理E（[8]） k≥5为奇数，G为K4-free k连通图，则G有k+1条可收缩边。三角形在可收缩边的研究中扮演了一个重要角色。Mader在（[9]）中证明了收缩临界k连通图中含有很多三角形，他得到了：定理F（[9]）设G是一个收缩临界k连通图，则G中至少有|V（G）|／3个三角形。而最近Kriesell在（[10]）中改进了Mader的结果，他证明了收缩临界k连通图中至少有2|V（G）|／3个三角形。一个bowtie是指一个由两个恰有一个公共顶点的三角形构成的图形，最近Ando等人在（[11]）中得到如下结果：定理G设k≥4是一个整数，若一个k连通图G中没有可收缩边，则G中含有bowtie。即，若一个k（k≥4）连通图G中不含bowtie，则G中含有可收缩边。通过仔细考察bowtie-free k连通图，我们在本文第一章中得到如下定理：定理1设G是无bowtie作为子图，也无H图作为导出子图的k连通图，则G中至少有k条可收缩边。（k≥4）。（图H=kK1+K2-{uy，vx}+{xy}，其中K2=uv，x，y∈V（kK1），即H中有一个4圈，且该圈恰有一条边在k-2个三角形上）。我们给出了一个例子，说明定理1中的k这个下界是一个较好的下界。定理2设G是无bowtie，也无（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+C4，不难发现，K1+C4即为P3+2K1。我们在第二章中得到了下面的结论：定理3若极小k（k≥5）连通图G中不含P3+3K1，且G中任意一个k度点x∈V（G），E（x）中有一条边不含在任何三角形中，则G中有一条k可收缩边。我们构造了一个5正则5连通图，含有K1+C4，但不含P3+3K1，每个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）。

论文目录

• 中文摘要
• 英文摘要
• 第一章 Bowtie-freek连通图中的k可收缩边
• §1.1 引言
• §1.2 某些定义及相关引理
• §1.3 定理1的证明
• §1.4 定理2的证明
• 第二章 极小k连通图中的k可收缩边
• §2.1 引言
• §2.2 相关引理
• §2.3 定理3的证明
• §2.4 定理3的推广
• 参考文献
• 致谢