Article ID Journal Published Year Pages File Type
419381 Discrete Applied Mathematics 2013 6 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). In 2004, Hellwig and Volkmann gave a sufficient condition for λ2λ2-optimality in graphs of diameter 2. In this paper, we extend the result and give a similar sufficient condition for λkλk-optimality in graphs of diameter 2 with k≥3k≥3.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,