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 Bonsma | 1 | 287 | 20.46 |
Nicola Ueffing | 2 | 693 | 70.42 |
Lutz Volkmann | 3 | 943 | 147.74 |