【作者】 赵博；

【导师】 吴吉昌；

【作者基本信息】 山东大学 ， 运筹学与控制论， 2012， 硕士

【摘要】 设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上的一个分裂,最后得到图记为Gx1x2,x3x4x其中V(Gx1x2,x3x4x)=V(G)-{x}, E(Gx1x2,x3x4x)=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-连通的.更多还原

【Abstract】 For a k-connected graph G and an edge e of the graph G, we denote by G/e the graph abtained from graph G by contraction of the edge e. If G/e is also k-connected, then edge e is said to be a k-contractible edge, and contractible edge for short, otherwise known as the non-contractible edge. Since contraction of a k-connected edge in a k-connected graph can be used to prove some properties for inductive arguments, the distribution of k-contraetible edges can be meaningful. If the edge xy in a triangle xyz, and d(z)=k, it is easy to see that the edge xy is not a contractible edge, which is known as the trivial non-contractiblc edges.In the paper, the splitting operation at a vertex of degree six in a6-connected graph is defined.Definition:let G be a6-connected graph and let x be a vertex of G of degree six. Let NG(x)={x1, x2, x3, x4, x5, x6}.Then we consider the following operation.(1) delete the vertex x,(2) add the edge x1x2if x1and x2are not already joined by an edge, and(3) add the edge x3x4if x3and x4are not already joined by an edge, and(4) add the edge x5xi if x5and xi are not already joined by an edge, i=1,2,3,4, and(5) add the edge x6xj if x6and xj are not already joined by an edge,3=1.2,3,4.5. We call this operation splitting at x, and denote the resulting graph by Gx1,x2,x3x4x.In other words, Gx1x2,x3x4x is the graph defined by V(Gx1x2,x3x4x)＝V(G)-{x}, E(Gx1x2,x3x4x)=E(G-x)∪{x1x2,x3x4,x5x6,xix5,xix6:i=1.2.3,4}.We consider splitting and contractible edges as tools for reduction of6-connected graphs. We prove the following theorem.Theorem:For a6-connected graph G of order at least eight, if the order of any end in graph G is not equal to two, and for any vertex z of degree6, G[NG(z)] contains a subgraph (K2∪2K1)+K2, then, for any x in V(G), one of the followings holds:(1) A6-contractible edge is incident with x:(2) There exists a vertex y of degree six in NG(x) such that a6-contractible edge is incident with y;(3) There exists a vertex y of degree six in NG(x) such that after some splitting at vertex y in graph G, and the resulting graph is also6-connected.更多还原