一致星因子图与笼的连通性

摘要

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连通的。在第三章里，我们将在前人研究的基础上，继续研究笼的连通性。

目录

文摘

英文文摘

声明

Chapter1 Introduction

1.1 Notations and terminology

1.2 Problems and backgrounds

Chapter2 Star-Uniform Graphs

2.1 Star-uniform graphs under a constant function

2.2 Star-uniform graphs under a general function

Chapter3 Connectivity of Cages

3.1 Introduction

3.2 New improvements on the connectivity of(k，g)—cages

3.3 Tightly superconnectivity of(4，g)—cages

Bibliography

致谢

个人简介