Edge-cuts leaving components of order at least three

摘要

Let G be a graph with vertex set V(G) and edge set E(G). For X is contained in V(G) let G[X] be the subgraph induced by X, X-bar = V(G) - X, and (x,X-bar) the set of edges in G with one end in X and the other in X-bar. If G is a connected graph and S is contained in E(G) such that G - S is disconnected, and each component of G - S consists of at least three vertices, then we speak of an order-3 edge-cut. The minimum cardinality |S| over all order-3 edge-cuts in G is called the order-3 edge-connectivity, denoted by λ_3 = λ_3(G). A connected graph G is λ_3-connected, if λ_3(G) exists. An order-3 edge-cut S in G is called a λ_3-cut, if |S| = λ_3. First of all, we characterize the class of graphs which are not λ_3=connected. Then we show for λ_3-connected graphs G that λ_3(G) ≤ ξ_3(G), where ξ_3(G) is defined by ξ_3(G) = min{|X,X-bar}|: X is contained in V(G), |X| = 3, G[X] is connected}. A λ_3-connected graph G is called λ_3-optimal, if λ_3(G) = ξ_3(G). If (X,X-bar) is a λ_3-cut, then X is contained in V(G) is called a λ_3-fragment. Let r_3(G) = min{|X|: X is a λ_3-fragment of G}. We prove that a λ_3-connected graph G is λ_3-optimal if and only if r_3(G) = 3. Finally, we study the λ_3-optimality of some graph classes. In particular, we show that the complete bipartite graph K_(r,s) with r,s ≥ 2 and r + s ≥ 6 is λ_3-optimal.