摘要
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.
Let G = （V, E） be a connected graph. X belong to 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.
基金
the National Natural Science Foundation of China (10671165)
Specialized Research Fund for the Doctoral Program of Higher Education of China (20050755001)
关键词
曲线图
连通性
集的势
周长
3-restricted cut, 3-restricted connectivity, girth
