论文部分内容阅读
1940年,Turan首先将极图理论作为一个学科来研究,Paul Erdos进而推动了这一理论的发展。自此,极图理论成为图论的一个重要分支。在极图理论里,我们所感兴趣的是图的各种不变量之间的关系,这些不变量包括顶点数、边数、连通度、最小度、直径等。此外,多大的这些不变量才能保证图具有某些性质,这也是我们所感兴趣的地方。通常对一类图H,给定性质p和一个不变量μ,我们希望确定出最小的值m,使得H中每个满足μ(G)>m的图G都具有性质p。我们称H中的那些不具有性质p且μ(G)=m的图G为此问题下的极图。举个例子,每个顶点数为n,边数至少为n的图一定包含圈,那么在这个问题下的极图就是所有顶点数为n的树。说到这里,我们需要强调下,本文中所说的极图理论是指广义的,它可以包括各种结构性结果。
在本文中,我们主要讨论了两类极图。一类是关于一致星因子图的刻画,另一类则是关于笼的连通性。在第一章中,我们将会介绍一些基本的定义和相关问题的历史背景。
我们称同构于K1,n的树为星,这里n≥1。如果图G的某个生成子图的所有分支都是星,则称这个生成子图足图G的一个星因子。图G的边赋权函数是指ω:E(G)→N+,这里N+表示正整数集合。设H是图G的一个子图,在G的边赋权函数ω下,图H上所有边的权和称为H的权,也就是说,ω(H)=∑e∈E(H)ω(e)。如果图G存在一个边赋权函数ω,使得G的每个星因子的权都相等,那么我们则称图G是一致星因子图。一致星因子图的概念是由Hartnell和Rall在文[24]中提出的。在第二章里,我们首先用Gallai-Edmonds匹配结构定理给出在常函数边赋权条件下,所有一致星因子图的完整刻画;然后给出在一般边赋权函数条件下,所有围长至少为5的一致星因子图的一个清晰刻画。
如果一个k-正则图G的围长为g,则称它为(k,g)-图。对给定的k和g,含有最少顶点数的(k,g)-图则称之为笼。笼问题是图论中最古老的问题之一。笼是由Tutte[52]在1947提出的,此后得到广泛地研究,然而这个课题太难了。一般来说,当k≥3,g≥5时,即使是估计笼的顶点数的界都是很困难的。因此,最近很多学者把精力放在对笼的结构性质研究上了,比如笼的连通性。在文章[Fu,Huang and Rodger,Connectivity of cages,J.Graph Theory,24(1997),187-191]中,他们猜想在k≥3时,所有(k,g)-笼都是k连通的。在第三章里,我们将在前人研究的基础上,继续研究笼的连通性。