کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649844 | 1342467 | 2009 | 10 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Mathematics - Volume 309, Issue 10, 28 May 2009, Pages 3336–3345