Title
Edge-cuts leaving components of order at least three
Abstract
Let G be a graph with vertex set V(G) and edge set E(G). For X ⊆ V(G) let G[X] be the subgraph induced by X,X = V(G) - X, and (X,X) the set of edges in G with one end in X and the other in X. If G is a connected graph and S ⊆ 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)|: X ⊆ 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) is a λ3-cut, then X ⊆ V(G) is called a λ3-fragment. Let r3(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 r3(G) = 3. Finally, we study the λ3-optimality of some graph classes. In particular, we show that the complete bipartite graph Kr,s with r,s ≥ 2 and r + s ≥ 6 is λ3-optimal.
Year
DOI
Venue
2002
10.1016/S0012-365X(02)00385-0
Discrete Mathematics
Keywords
Field
DocType
3-connected graph,order-3 edge-connectivity,graph class,connected graph,order-3 edge-cuts,order-3 edge-cut,minimum cardinality,complete bipartite graph,atoms
Complete graph,Complete bipartite graph,Discrete mathematics,Combinatorics,Bound graph,Vertex (geometry),Subgroup,Bipartite graph,Cardinality,Connectivity,Mathematics
Journal
Volume
Issue
ISSN
256
1-2
Discrete Mathematics
Citations 
PageRank 
References 
44
1.98
4
Authors
3
Name
Order
Citations
PageRank
Paul Bonsma128720.46
Nicola Ueffing269370.42
Lutz Volkmann3943147.74