论文部分内容阅读
如果将k连通图G中的一条边收缩之后所得到的图仍然k连通,川称这条边为G的k可收缩边。利用队至少是5的3连通图中存在3可收缩边这一性质,_1980年Thomassen使用归纳法统一证明了关于平面图的Kuratowski等三个重要定理.自那以来,人们对k连通图中k可收缩边进行了大量的研究不存在k可收缩边的完全k连通图称为收缩临界k连通图.由于收缩临界k连通图每一个性质的否定都可得到k连通图中存在k可收缩边的允分条什,因而对k连通图中k可收缩边进行研究就转化为对收缩临界k连通图性质的研究。
最先Egowa证明每一个收缩临界k连通图有一个基数小于等于k/4的断片,由此可推出当k=4,5,6,7时,收缩临界k连通图的最小度等于k.已经知道不存在收缩临界3连通图,收缩临界4连通图的结构已经完全清楚,它们是两炎特殊的4正则力,接着自然要想弄清收缩临界5连通图的结构,经过多年的探索,人们发现这是一个十分困难的问题.为了弄清收缩临界5连通图的结构,首先要了解收缩临界5连通图性质.山前面Egawa的结果知道收缩临界5连通图至少有一个5度顶点,对于收缩临界5连通图中5度顶点的分布,袁旭东在1994年得到:
定理A 收缩临界5连通图中每一个点都与1个5度点相邻。
由此可以推出G中至少有1/5│G│个5度顶点。1997年苏健基进一步证明了:
定理B 收缩临界5连通图中每一个点都与2个5度点相邻。
由此可以推出G中至少有2/5│G│个5度顶点.到了2003午,Ando又重复得到袁在1994年得到的结果.对于收缩临界5连通图G中5度顶点数的下界,最近覃城阜改进到:
定理C 设G是收缩临界5连通图,则G至少有4/9│G│个5度顶点。
本文进一步得到:
定理1 若G为收缩临界5连通图,则G中至少有1/2│G│个5度顶点。
对于收缩临界k连通图G,最早Thomassen证明图中都有三边形,后来Mader改进到有│G│/3个三边形,最近Kriesell证明至少有2│G│/3个三边形山丁收缩临界5连通图中有很多三边形,又有很多5度顶点,因而也会有不少通过5度顶点的三边形.如果k连通图的一条边在三边形上,并且它所对的顶点是k度顶点,也即这条边的两个端点有一个公共邻点是k度点,这条边显然是不可收缩边,称为平凡不可收缩边.Ando研究了收缩临界5连通图中平凡不可收缩边的分布,证明了:
定理D 收缩临界5连通图G至少有1/2│G│条平凡不可收缩边。
他还提出猜想:
猜想收缩临界5连通图G至少有2│G│条平凡不可收缩边。
最近李向军证明了:
定理E 收缩临界5连通图G至少有│G│+1条平凡不可收缩边。
本文在此基础上进一步得到:
定理2 若G为收缩临界5连通图,则G中至少有3/2│G│条平凡不可收缩边。