Article ID Journal Published Year Pages File Type
4649844 Discrete Mathematics 2009 10 Pages PDF
Abstract

For a positive integer mm, an edge-cut SS of a connected graph GG is an mm-restricted edge-cut if each component of G−SG−S contains at least mm vertices. The mm-restricted edge connectivity of GG, denoted by λm(G)λm(G), is defined as the minimum cardinality of all mm-restricted edge-cuts. Let ξm(G)≔min{|∂(X)|:X⊆V(G),|X|=m, and G[X] is connected}ξm(G)≔min{|∂(X)|:X⊆V(G),|X|=m, and G[X] is connected}, where ∂(X)∂(X) denotes the set of edges of GG each having exactly one endpoint in XX. A graph GG is said to be λmλm-optimal if λm(G)=ξm(G)λm(G)=ξm(G), and super-λmλm if every minimum mm-restricted edge-cut isolates a component of size exactly mm.In this paper, firstly, we give some relations among λ3λ3-optimal, λiλi-optimal and super-λiλi for i=1,2i=1,2. Then we present degree conditions for arbitrary, triangle-free and bipartite graphs to be λ3λ3-optimal and super-λ3λ3, respectively; moreover, we give some examples which prove that our results are the best possible.

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