k-连通图中的可收缩团

来源 :南开大学 | 被引量 : 0次 | 上传用户:a932632391
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
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等人所做结果的推广;在第三章里,我们给出了证明主要定理所需的四个引理以及它们的证明;在第四章中,我们给出了主要结论的完整证明过程。
其他文献
De-Sitter不变相对论是从相对性原理与不变普适常数原理出发,在de-Sitter时空中建立的一类相对论。爱因斯坦狭义相对论是这类相对论在曲率半径趋于无限的退化形式。在这类相对
近几年,一些新型的传染病如SARS,禽流感出现了,在很短的时间里,迅速的在我国和全球一些国家爆发流行,极大的威胁到人类的身体健康和生命安全,直接影响到社会稳定和经济发展。对于这
积分方程广泛应用在信号传送、生物数学、断裂力学、原子物理、神经网络、交通运输等众多工程科学的数学模型中,所以对积分方程的研究是非常有意义的,特别是第二类Fredholm积分
有根树具有非线性结构,在组合数学中占有重要的地位。有序树是一类特殊的有根树,其节点的子树具有序关系。格路与有根树有着紧密的联系,利用格路语言,本文给出了一些等式的组合证
球定理一直是整体微分几何中的核心问题,并且由它推动了比较几何中大量问题的发展,产生了许多新的思想和方法,已经构成了微分几何中最强大的分支之一. U.Abresch和W.T.Meyer