论文部分内容阅读
k-连通图G的一条边或一个子图是k-可收缩的,如果这条边或这个子图收缩后所得的图仍是k-连通的。图的团是指图中极大的完全子图。Tutte证明了下面著名的结果:任意顶点数大于或等于5的3-连通图都含有一条3-可收缩边。C.Thomassen证明了任意不含三角形的k-连通图都有一条k-可收缩的边。这里的三角形是指长为3的圈。Kawarabayashi证明了对于某个整数k≥4,任意的k-连通图或者含有共享一条边的两个三角形,或者含有一条k-可收缩的但不包含在任何三角形中的边,或者含有一个k-可收缩的但不与其它三角形共享一条边的三角形。显然,Kawarabayashi的结果包含了C.Thomassen的结论。Tutte、Kawarabayashi和Thomassen等人的研究只是侧重于k-连通图中顶点数比较少的可收缩子图的存在性,如边或者三角形。另外一些研究者则对连通度作了限制,一般研究3-连通图、4-连通图、5-连通图、6-连通图。还有一些学者则是侧重于一类对了图有限制的连通图的可收缩边的研究。在这篇论文里,我们研究了k-连通图中子图的顶点数比较多时k-可收缩子图的存在性。结果表明这种可收缩子图的存在性依赖于共享一条边的三角形的数目。我们推广了Kawarabayashi的技巧,并证明了一个更一般的有关k-可收缩团的结论。
我们证明了对于t≥0和k≥max{4,t+3},任意k-连通图G或者包含有一个顶点数最多为t+2的可收缩团,或者有一条边包含在G的t+1个三角形中,或者存在G中的两个团至少共享一条边,或者图G中有一个顶点数大于或等于4和一个顶点数大于或等于3的团,它们的交是非空的。
本论文分为以下四个部分:在第一章里,我们给出了本文所用到的一些相关的图论定义,并且回顺了k-连通图中k-可收缩子图这个问题的背景和已有的结果;在第二章里,我们给出了本文的主要定理,并且指出该定理是Tutte、Kawarabayashi和C.Thomassen等人所做结果的推广;在第三章里,我们给出了证明主要定理所需的四个引理以及它们的证明;在第四章中,我们给出了主要结论的完整证明过程。