Article ID Journal Published Year Pages File Type
4650160 Discrete Mathematics 2009 12 Pages PDF
Abstract

For a connected graph G=(V,E)G=(V,E), an edge set S⊆ES⊆E is a kk-restricted edge cut if G−SG−S is disconnected and every component of G−SG−S has at least kk vertices. The kk-restricted edge connectivity of GG, denoted by λk(G)λk(G), is defined as the cardinality of a minimum kk-restricted edge cut. Let ξk(G)=min{|[X,X¯]|:|X|=k,G[X]is connected}. GG is λkλk-optimal if λk(G)=ξk(G)λk(G)=ξk(G). Moreover, GG is super-λkλk if every minimum kk-restricted edge cut of GG isolates one connected subgraph of order kk. In this paper, we prove that if |NG(u)∩NG(v)|≥2k−1|NG(u)∩NG(v)|≥2k−1 for all pairs uu, vv of nonadjacent vertices, then GG is λkλk-optimal; and if |NG(u)∩NG(v)|≥2k|NG(u)∩NG(v)|≥2k for all pairs uu, vv of nonadjacent vertices, then GG is either super-λkλk or in a special class of graphs. In addition, for kk-isoperimetric edge connectivity, which is closely related with the concept of kk-restricted edge connectivity, we show similar results.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,