SHANDONG SCIENCE ›› 2015, Vol. 28 ›› Issue (3): 80-83.doi: 10.3976/j.issn.1002-4026.2015.03.015

• Other Research Article • Previous Articles     Next Articles

Sufficient conditions of a maximally 3restricted edge connected graph

WANG Meiyu, WANG Shiying   

  1. School of Mathematics Sciences, Shanxi University, Taiyuan 030006, China
  • Received:2014-10-07 Online:2015-06-20 Published:2015-06-20

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

CLC Number: 

  • O157.5