On the restricted connectivity and superconnectivity in graphs with given girth
On the restricted connectivity and superconnectivity in graphs with given girth
复制标题
DOI：
10.1016/j.disc.2006.07.016
复制
发表时间：
2007-03
期刊：
影响因子：
--
通讯作者：
C. Balbuena;M. Cera;A. Diánez;P. García-Vázquez;X. Marcote
中科院分区：
文献类型：
--
作者：
C. Balbuena;M. Cera;A. Diánez;P. García-Vázquez;X. Marcote
连通图G的限制连通度κ '（G）被定义为所有顶点割X上的顶点割的最小基数，使得没有顶点u在X中拥有所有邻居;超连通度κ1（G）的定义类似，这次只考虑G-X中的顶点u，因此κ1（G）κ'（G）。图G的最小边度为n（G）=min{d（u）+d（v）-2：uv∈E（G）}，d（u）表示顶点u的度.本文给出了产生κ1（G）的几个充分条件，改进了Fiol等[Short routes and connectivity in graphs and digraphs，Ars Combin. 29 B（1990）17-31]，并在某些附加约束下保证κ1（G）=κ′（G）= κ（G）。
The restricted connectivity κ′(G) of a connected graph G is defined as the minimum cardinality of a vertex-cut over all vertex-cuts X such that no vertex u has all its neighbors in X; the superconnectivity κ1(G) is defined similarly, this time considering only vertices u in G-X, hence κ1(G)⩽κ′(G). The minimum edge-degree of G is ξ(G)=min{d(u)+d(v)-2:uv∈E(G)}, d(u) standing for the degree of a vertex u. In this paper, several sufficient conditions yielding κ1(G)⩾ξ(G) are given, improving a previous related result by Fiol et al. [Short paths and connectivity in graphs and digraphs, Ars Combin. 29B (1990) 17–31] and guaranteeing κ1(G)=κ′(G)=ξ(G) under some additional constraints.