图是极大3限制边联通的充分条件  

Sufficient conditions of a maximally 3-restricted edge connected graph

作　　者：王美玉[1] 王世英[1] 

机构地区：[1]山西大学数学科学学院,山西太原030006

出　　处：《山东科学》2015年第3期80-83,共4页Shandong Science

基　　金：国家自然科学基金(6137001);国家自然科学基金青年科学基金(11401354);教育部博士点基金(博导类)(20111401110005)

摘　　要：设S是连通图G中的一个边子集。若G-S不连通且它的每个连通分支的阶至少为k,则称S是G的一个k限制边割。图G的最小k限制边割的边数称为G的k限制边连通度,记为λκ(G)。定义ξκ(G)=min{|[X,]|:|X|=k,G[X]连通},其中=V(G)\X。若λk(G)=ξk(G),则称G是极大k限制边连通的。设G是一个围长至少为5的λ3-连通图。本文证明了若G中不存在5个点u1,u2,v1,v2,v3使得d(ui,vj)≥3(i=1,2;j=1,2,3),则G是极大3限制边连通的。Let S be an edge subset in a connected graph G. S is a κ -restricted edge cut if G-S is disconnected and the order of its every connected branch is at least k. The cardinality of a minimum k-restricted edge cut of graph G is denoted by λκ（G）.Letξk（G） =min{丨[X,X] 丨：丨X丨 =k,G[X]is connected}, where X= V（G）／X. A graph G is maximally k-restricted edge connected if λκ（G） =ξk（G）. Let G be a 2,3-connected graph with girth more than five. We prove that G is maximally 3-restricted edge connected if it does not contain five vertices u1, u2, v1, v2, v3 satisfying d （ ui, vj） ≥3 （i = 1,2; j=1,2,3）.

关 键 词：连通图 k限制边连通度 距离 围长 

分 类 号：O157.5[理学—数学]