Sufficient conditions for super k-restricted edge connectivity in graphs of diameter 2
Sufficient conditions for super k-restricted edge connectivity in graphs of diameter 2
复制标题
DOI：
10.1016/j.disc.2008.01.037
复制
发表时间：
2009-03
期刊：
影响因子：
--
通讯作者：
Shiying Wang;Shangwei Lin;Chunfang Li
中科院分区：
文献类型：
--
作者：
Shiying Wang;Shangwei Lin;Chunfang Li
对于连通图G=(V，E)，如果G−S不连通且G−S的每个分量至少有k个顶点，则边集S∈E为k限制边切。G的k限制边连通性用λk(G)表示，定义为最小k限制边切割的基数。设ξk(G)=min{|[X,X¯]|:|X|=k，G[X]已连接}。当λk(G)=ξk(G)时，G为λk最优。此外，如果G的每一个最小k限制边切割分离出一个k阶的连通子图，则G是超λk的。本文证明了如果|NG(u)∩NG(v)|≥2k−1对于所有非相邻顶点对u， v，则G是λk最优的；如果|NG(u)∩NG(v)|≥2k对于所有非相邻顶点对u， v，则G在一个特殊的图类中要么是超λkor。此外，对于与k限制边连通性概念密切相关的k等周边连通性，我们也得到了类似的结果。
For a connected graph G=(V,E), an edge set S⊆E is a k-restricted edge cut if G−S is disconnected and every component of G−S has at least k vertices. The k-restricted edge connectivity of G, denoted by λk(G), is defined as the cardinality of a minimum k-restricted edge cut. Let ξk(G)=min{|[X,X¯]|:|X|=k,G[X]is connected}. G is λk-optimal if λk(G)=ξk(G). Moreover, G is super-λkif every minimum k-restricted edge cut of G isolates one connected subgraph of order k. In this paper, we prove that if |NG(u)∩NG(v)|≥2k−1 for all pairs u, v of nonadjacent vertices, then G is λk-optimal; and if |NG(u)∩NG(v)|≥2k for all pairs u, v of nonadjacent vertices, then G is either super-λkor in a special class of graphs. In addition, for k-isoperimetric edge connectivity, which is closely related with the concept of k-restricted edge connectivity, we show similar results.