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

Abstract: Let S be an edge subset in a connected graph G. S is a k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 ξκ(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 λk(G)=ξk(G). Let G be a λ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).

Key words: krestricted edge connectivity, girth, connected graph, distance