| 3-restricted connectivity of graphs with given girth |
| |
| 作者单位： | GUO Li-tao MENG Ji-xiang College of Math.and Sys.Sci.，Xinjiang Univ.，Xinjiang 830046，China. |
| |
| 基金项目： | 国家自然科学基金，高等学校博士学科点专项科研项目 |
| |
| 摘 要： | 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.
|
| 关 键 词： | 曲线图 连通性 集的势 周长 |
3-restricted connectivity of graphs with given girth |
| |
| Authors: | Li-tao Guo Ji-xiang Meng |
| |
| Institution: | College of Math. and Sys. Sci., Xinjiang Univ. Xinjiang 830046, China |
| |
| Abstract: | 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.
Supported by the National Natural Science Foundation of China (10671165) and Specialized Research Fund for the Doctoral Program
of Higher Education of China (20050755001) |
| |
| Keywords: | 3-restricted cut 3-restricted connectivity girth |
| 本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录！ |
