3-restricted connectivity of graphs with given girth

被引:0
作者
Li-tao Guo
Ji-xiang Meng
机构
[1] Xinjiang Univ.,College of Math. and Sys. Sci.
来源
Applied Mathematics-A Journal of Chinese Universities | 2008年 / 23卷
关键词
3-restricted cut; 3-restricted connectivity; girth; 05C;
D O I
暂无
中图分类号
学科分类号
摘要
Let G = (V,E) be a connected graph. X ⊂ V (G) is a vertex set. X is a 3-restricted cut of G, if G-X is not connected and every component of G-X has at least three vertices. The 3-restricted connectivity κ3(G) (in short κ3) of G is the cardinality of a minimum 3-restricted cut of G. X is called κ3-cut, if |X| = κ3. A graph G is κ3-connected, if a 3-restricted cut exists. Let G be a graph girth g ≥ 4, ξ3(G) is min{d(x) + d(y) + d(z) − 4: xyz is a 2-path of G}. It will be shown that κ3(G) = ξ3(G) under the condition of girth.
引用
收藏
页码:351 / 358
页数:7
相关论文
共 22 条
  • [1] Balbuena C.(2007)On the restricted connectivity and superconnectivity in graphs with given girth Discrete Math 307 659-667
  • [2] Cera M.(2006)Sufficient conditions for J Graph Theroy 52 73-86
  • [3] Diánez A.(2002)-optimality in graphs with girth Discrete Math 256 431-439
  • [4] Balbuena C.(1988)Edge-cuts leaving components of order at least three Inform Process Lett 27 195-199
  • [5] Garcia-Vázquez P.(1994)On computing a conditional edge connectivity of a graph Discrete Math 127 163-170
  • [6] Marcote X.(2002)Extraconnectivity of graphs with large girth Discrete Appl Math 117 183-193
  • [7] Bonsna P.(2005)On a kind of restricted edge connectivity of graphs Discrete Math 305 365-371
  • [8] Ueffing N.(2002)Edge cuts leaving components of order at least Discrete Math 258 205-214
  • [9] Volkmann L.(2002)Conditional edge connectivity properties, reliability comparison and transitivity of graphs Discrete Math 243 291-298
  • [10] Esfahanian A.(2007)On restricted edge connectivity of graphs Discrete Math 307 293-298