收缩临界k连通图中的原子及阶较小的端片

论文摘要

本文主要研究收缩临界k连通图，如果将k连通图G中的一条边收缩之后所得到的图仍然是k连通图，则称这条边为G的k可收缩边，简称可收缩边，否则称为不可收缩边。1961年Tutte[20]证明了阶至少是5的3连通图有可收缩边，利用这一结论，Thomassen用归纳法统一证明了平面图的一些性质，由此引发了人们对一股k连通图中可收缩边的研究。不存在可收缩边的非完全k连通图称为收缩临界k连通图。对于k≥4，Thomassen[19]证明了存在无限多个k连通k正则图，这一类图中不含有k可收缩边，由于收缩临界k连通图每一个性质的否定都可得到k连通图中存在k可收缩边的充分条件，因而研究收缩临界k连通图的性质是十分有意义的。对于收缩临界k连通图，Egawa[3]首先证明了：定理A若G是收缩临界k连通图，则G中原子的基数不超过k／4。由这定理A知：若G是收缩临界的，则G是4连通的，因此收缩临界4连通图是连通度最小可能的收缩临界图。Martinov[13]清楚地刻画了收缩临界4连通图：只有圈的平方Cn2（n≥5）及圈4连通3正则图的线图这两类。对于k=5，6，7，由定理A知每个收缩临界k连通图都有一个k度点。围绕该类图人们进行了广泛的研究，已有了比较好的认识（[21][17][16]等）。但对于k≥8，收缩临界k连通图G却不一定有k度点。因而对这类图研究其原子及阶较小的端片是切实可行的，后来苏健基[15]推广了Egawa的结果：定理B若G是收缩临界k连通图，则G中存在两个不相交的断片A，B，使得|A|+|B|≤k／2。最近Kriesell（[9]）进一步加强，得到：定理C每一个收缩临界k连通图G有两个不相交的断片A，B，使得|A|+|B|≤2「k／4」。苏健基在文献[15]中运用定理B证明了：定理D设G是收缩临界k连通图，如果δ（G）=5k／4-1，即k能被4整除，那么G有4个阶为k／4的原子，因而G中至少有4×k／4=k个最小度点。苏猜想定理D中G的原子数目的下界”4”有可能改进到”6”，如果成立，那么[4]中的例子将说明”6”是最好可能的，最近这一猜想已被袁旭东等[18]与Kriesell[9]分别证明：定理E设G是收缩临界k连通图，如果δ=（G）=5k／4-1，即k能被4整除，那么G有6个阶为k／4的原子，因而G中至少有6×k／4=3k／2个最小度点。对于收缩临界k连通图G，令k=4q+r（0≤r≤3），则q=「k／4」。如果r≠0且G中有一个原子A的基数等于q，由定理E人们自然会问G中是否还有另外原子?对此本文进行了探索，得到：定理1设G是收缩临界k连通图，如果δ（G）=「5k／4」-1且k=4q+1，那么G有5个基数是q的原子，因而G中至少有5「k／4」=5q个最小度点。设G是收缩临界k连通图，k=4q+r（0≤r≤3），G中原子A的基数为q-1，那么由定理C知G中有另一个与A不相交的端片B使得|B|≤q+1。对于这样的端片B其基数是否可以再小一些呢?对此本文得到以下结果：定理2设G是收缩临界k=4q+r（0≤r≤2，q≥2）连通图，如果G的原子A的阶为q-1，则G中有另一个与A不相交的端片B，使得|B|≤q。

论文目录

• 中文摘要
• 英文摘要
• 目录
• 第一章 引言
• 第二章 定理1的证明
• 第三章 定理2的证明
• 第四章 可进一步考虑的问题
• 参考文献
• 致谢