收缩临界6连通图中6度顶点数新的下界

论文摘要

对于F（?）V（G），记NG（F）=(∪x∈FNG（x）)-F。设G是非完全图，T是最小点割，F是G-T的至少一个分支但不是所有分支的并，则称F是G的断片，或T-断片。（?）=G-T-F，那么（?）也是T-断片。这时我们称F，（?）是T分离G所得的两个断片。若F是断片，但F的任何真子集都不是G的断片，则称F为G的端片。阶最小的断片，称为原子。为方便起见，我们常常将V（F）与F等同起来。x∈V（G），G中与x关联的所有边的集合记为E（x）。设F是图G一个断片，x∈V（G），如果N（F）包含E（x）中某一条边的2个端点，则称F是一个E（x）-断片。如果将k连通图G中的一条边e收缩之后所得到的图是一个k连通图，那么这条边e就叫做G的k可收缩边，简称可收缩边。1961年Tutte证明了阶至少是5的3连通图有可收缩边（[15]）。之后人们对3连通图中的可收缩边进行了广泛的研究，在3连通图中可收缩边的分布和可收缩边条数的下界等方面都得到了许多结果（[4]）。对于k≥4，Thomassen[14]证明了存在无限多个k连通k正则图，这一类图中不含有k可收缩边。一个k连通非完全图G若不含有k可收缩边，那么G叫做收缩临界k连通图。为得到k连通图中存在可收缩边的条件，很自然要对收缩临界k连通图（k≥4）进行研究。对于k=4，Martinov[12]清楚地刻画了收缩临界4连通图，即：收缩临界4连通图只有两类：一类是圈的平方，另一类是圈4连通3正则图的线图。当k≥5时，收缩临界k连通图的刻画要困难得多。一般地，Egawa[5]证明了每个收缩临界k连通图（k≥4）都存在一个阶至多是k／4的断片，由此我们知道每个收缩临界k连通图中都有一个度至多是∈「（5k）／4」-1的点。因此，对于5≤k≤7，每个收缩临界k连通图都有一个k度点。近年来人们围绕收缩临界k连通图中k度顶点的分布以及该类图中k度顶点数的下界做了大量的工作[2]。用Vk（G）表示图G中k度点的集合。Ando等人提出如下问题：问题设k是一个整数且5≤k≤7，对收缩临界k连通图，是否存在一个常数ck，使得|Vk|≥ck|V（G）|。若有，试确定ck的最大值?对于收缩临界5连通图，袁旭东在1994年得到：收缩临界5连通图中每一个点都与1个5度点相邻。由此可以推出G中至少有1／5|G|个5度顶点。1997年苏健基进一步证明了：收缩临界5连通图中每一个点都与2个5度点相邻。由此可以推出G中至少有2／5|G|个5度顶点。到了2003年，Ando又重复得到袁在1994年得到的结果。最近覃城阜把以上结果改进到：设G是收缩临界5连通图，则|V5（G）|≥4／9|G|。对于k=6，袁旭东和苏健基在[20]中证明了下面的结果：定理A每个收缩临界6连通图都有两个相邻的6度点。齐恩凤，袁旭东对这一结果做了如下改进：定理B设x是收缩临界6连通图中的一个6度顶点，则或者它与一个6度顶点相邻，或者在它的邻域中存在一点y，在y的邻域中有两个相邻的6度顶点。对于收缩临界6连通图，Ando等人([1]证明了以下性质：定理C设G是收缩临界6连通图，H=G[V6（G）]。则对任一x∈W，都存在一个E（x）-断片A，使得（1）H[N（A）∩V6（G）]（?）2K2或（2）W（G）∩N（A）={x}，H[N（A）∩V6（G）]（?）K2∪K1。利用定理C，Ando等人得到了：定理D收缩临界6连通图G中至少有|G|／7个6度顶点。2005年，赵巧凤和覃城阜等人将这一结果改进为：定理E收缩临界6连通图G中至少有|G|／5个6度点。本文进一步对定理E做了改进，得到：定理1收缩临界6连通图G中至少有|G|／4个6度顶点。

论文目录

• 中文摘要
• 英文摘要
• 收缩临界6连通图中的6度点数的新的下界
• §1.1 引言
• §1.2 断片的一些性质
• §1.3 定理1的证明
• 参考文献
• 致谢