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