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 Published:2015-06-20 Online: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

Open Access This article is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License (CC BY-NC 4.0), which permits third parties to freely share (i.e., copy and redistribute the material in any medium or format) and adapt (i.e., remix, transform, or build upon the material) the articles published in this journal, provided that appropriate credit is given, a link to the license is provided, and any changes made are indicated. The material may not be used for commercial purposes. For details of the CC BY-NC 4.0 license, please visit: https://creativecommons.org/licenses/by-nc/4.0