论文部分内容阅读
哈密顿圈问题是数学和计算机科学中最重要的问题之一,它也与著名的四色定理有着密切联系。1931年,Whitney在《Annals of Mathematics》中发表文章证明了每一个4连通平面三角剖分图都含有哈密顿圈(因此,也是4面可着色的)。1956年,Tutte把Whitney的结果推广到所有4连通平面图,而后Thomassen在1983年对此作了进一步拓展。这些证明是借助于某些特殊的路和圈的存在性加以归纳而得到的(后来称这些特殊的路和圈为Tutte子图)。Tutte子图方法如今已经被广泛应用到证明可嵌入各种曲面的图中长路和长圈的存在性。例如:Thomasen在1983年证明了Plummer提出的猜想一每一个4连通平面图都是哈密顿连通的,Thomas和郁星星解决了多面体领域的权威Grunbaum在1970年提出的把Tutte的结果推广到射影平面的猜想一所有4连通射影平面图都含有哈密顿圈,郁星星在1997年证明了Thomassen提出的猜想一所有(定向和非定向)曲面上的5连通“局部平面”三角剖分图都含有哈密顿圈,等等。在本文中,通过运用Tutte子图方法,我们主要得到两个结果。第一个是关于Malkevitch在1988年提出的一个猜想(第二章),第二个是关于3连通3正则不含三角形的平面图中的最大二部子图问题(第三章)。在第一章中,我们主要介绍在本文中用到的一些基本定义和记号,并给出关于Tutte子图方法的一个简要概述。在第二章中,我们考虑Malkevitch提出的猜想一如果一个n个顶点的4连通平面图含有长度为4的圈,那么它一定含有长度为k的圈,其中k∈{n,n-1,…,3}。已有的结果证明了每一个n个顶点的4连通平面图都含有长度为k的圈,其中k∈{n,n-1,…,n-6}且k≥3。通过运用Tutte子图和可收缩子图的方法,我们证明每一个n个顶点(n≥9)的4连通平面图总是含有不包含某一给定顶点的长度为n-6的圈。运用这一结果(以及Fontet和Martinov的一个定理),我们进一步证明每一个n个顶点(n≥10)的4连通平面图都含有长度为n-7的圈。在第三章中,我们研究3连通3正则不含三角形的平面图中的最大二部子图问题。最近,Thomassen证明了每一个3连通3正则不含三角形的平面图G中都含有一个至少有29|V(G)|/24-7/6条边的二部子图,改进了已知的(3正则不含三角形的图的)下界6|V(G)|/5。很容易可以看出,如果S是平面图G的一个边子集合使得G-S是一个二部图,则在G的对偶图中删除S所对应的边后得到的图是一个偶图。通过运用这一性质以及Tutte子图方法,Thomassen证明了如下等价结果:每一个最小度至少为4的平面三角剖分图G都含有一个至多有7|V(G)|/12条边的边子集合使得在G中删除这些边后得到的图是一个偶图。我们通过拓展Thomassen在Tutte圈上的结果将上界改进到9|V(G)|/16-9/16,这表明每一个3连通3正则不含三角形的平面图G中都含有一个至少有39|V(G)|/32-9/16条边的二部子图。