论文部分内容阅读
设G是k-连通图，e为图G的边，图G收缩边e后所得的图记为G/e，若G/e仍为k-连通图，则称e为图G的k可收缩边，简称可收缩边.否则称为不可收缩边(.)如果k-连通图中存在可收缩边，则可使用归纳法去证明k-连通图的某些性质，因此研究图的可收缩边是很有意义的，在k-连通图中，若边xy在一个三角形xyz上，且d（z）=k，易见xy不是可收缩边，图中这样的不可收缩边称为平凡的不可收缩边.
本文引入6-连通图中度为6的顶点的分裂运算，定义如下:
定义:设x为6-连通图G中度为6的顶点，NG(x）={x1，x2，x3，x4，x5，x6}.对图G作下列运算:
(1)从图G中去掉顶点x得图G-x;
(2)若顶点x1，x2不相邻，则加边x1x2;
(3)若顶点x3，x4不相邻，则加边x3x4;
(4)若顶点x5与xi不相邻，则加边xix5，其中i=1，2，3，4;
(5)若顶点x6与xj不相邻，则加边xjx6，其中j=1，2，3，4，5.
称上述运算为图G在顶点x上的一个分裂，最后得到图记为Gxx1x2，x3x4，其中V（Gxx1x2，x3x4）=V(G)-{x}，E(Gxx1x2，x3x4)=E(G-x)∪{x1x2,x3x4,x5x6,xix5, xix6(:)i=1,2,3,4}.
利用分裂和收缩的运算，对6-连通图进行归纳，证明的主要结论如下:
定理:对于阶至少为8的6-连通图G，如果图G的任一断片的阶不等于2，且对图G中的任一6度顶点z，G[NG(z)]中含子图(K2∪2K1)+K2，那么对图G中的任一顶点x，下列结论之一成立:
(1)x关联一条可收缩边;
(2)在NG(x)中存在一个6度顶点y关联一条可收缩边;
(3)在NG(x)中存在一个6度顶点y，使得对y作某一个分裂运算所得的图仍然是6-连通的.