Sufficient conditions for super k-restricted edge connectivity in graphs of diameter 2

AbstractFor 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-λk if 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-λk or 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