论文部分内容阅读
本文主要研究收缩临界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连通图，Egaur[3]首先证明了：
定理A 若G是收缩临界k连通图，则G中原子的基数不超过k／4.
由这定理A知：若G是收缩临界的，则G是4连通的，因此收缩界4边通图是连通度最小可能的收缩临界图。Martinou[13]清楚地刻画了收缩临界4连通图：只有圈的平方C2n(n≥5)及圈4连通3正则图的线图这两类。对于k=5,6,7,由定理A知每个收缩临界k连通图都有一个k度点。围绕该类图人们进行了广泛的研究。已有了比较好的认识（[21][17][16]等）。但对于k≥8,收缩临界k连通图G却不一定有k度点。因而对这类图研究其原子及阶较小的端片是切实可行的，后来苏健基［15］推广了Egaua的结果：
定理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]=5fq个最小度点。
设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≤r2,q≥2）连通图。如果G的原子A 阶为q-1,则G中有另一个与A不相交的端片B，使得｜B｜≤q.