Diameter-girth sufficient conditions for optimal extraconnectivity in graphs
Diameter-girth sufficient conditions for optimal extraconnectivity in graphs
复制标题
DOI：
10.1016/j.disc.2007.07.012
复制
发表时间：
2008-08
期刊：
影响因子：
--
通讯作者：
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，第 r 个额外连通性 κr(G) 被定义为割集 X 的最小基数，使得删除 X 的顶点后所有剩余分量至少具有 r+1 个顶点。标准连通性和超连通性分别对应于κ0(G)和κ1(G)。 G 的最小 r 树度，用 ψr(G) 表示，是 N(T) 在所有树 T⊆G 上的最小基数 |V(T)|=r+1，N(T) 是不在 T 中且与 T 的某个顶点相邻的顶点的集合。当 r=1 时，任何这样的考虑的树只是 G 的一条边。然后，ψ1(G) 等于所谓的 G 的最小边度，定义为 xi(G)=min{d(u)+d(v)-2:uv ∈ E(G)}，其中 d(u) 代表顶点 u 的度数。图 G 被称为最优 r 外连通，简称 κr 最优，如果 κr(G)⩾ Σr(G)。在本文中，我们提出了一些保证 r⩾2 的 κr(G)⩾Σr(G) 的充分条件。这些结果改进了之前的一些相关结果，并且可以看作是作者在 r=1 时获得的其他一些结果的补充。
For a connected graph G, the rth extraconnectivity κr(G) is defined as the minimum cardinality of a cutset X such that all remaining components after the deletion of the vertices of X have at least r+1 vertices. The standard connectivity and superconnectivity correspond to κ0(G) and κ1(G), respectively. The minimum r-tree degree of G, denoted by ξr(G), is the minimum cardinality of N(T) taken over all trees T⊆G of order |V(T)|=r+1, N(T) being the set of vertices not in T that are neighbors of some vertex of T. When r=1, any such considered tree is just an edge of G. Then, ξ1(G) is equal to the so-called minimum edge-degree of G, defined as ξ(G)=min{d(u)+d(v)-2:uv∈E(G)}, where d(u) stands for the degree of vertex u. A graph G is said to be optimally r-extraconnected, for short κr-optimal, if κr(G)⩾ξr(G). In this paper, we present some sufficient conditions that guarantee κr(G)⩾ξr(G) for r⩾2. These results improve some previous related ones, and can be seen as a complement of some others which were obtained by the authors for r=1.