Path graph

In graph theory, a graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.

Formal definition

Let $G=(V,E)$ be an arbitrary graph. If subgraph $G^{\prime }=(V,E\setminus X)$ is connected for all $X\subseteq E$ where $\left|X\right|<k$, then G is k-edge-connected. Trivially, a graph that is k-edge-connected is also (k−1)-edge-connected.

Relation to minimum vertex degree

Minimum vertex degree gives a trivial upper bound on edge-connectivity. That is, if a graph $G=(V,E)$ is k-edge-connected then it is necessary that k ≤ δ(G), where δ(G) is the minimum degree of any vertex v ∈ V. Obviously, deleting all edges incident to a vertex, v, would then disconnect v from the graph.

Computational aspects

There is a polynomial-time algorithm to determine the largest k for which a graph G is k-edge-connected. A simple algorithm would, for every pair (u,v), determine the maximum flow from u to v with the capacity of all edges in G set to 1 for both directions. A graph is k-edge-connected if and only if the maximum flow from u to v is at least k for any pair (u,v), so k is the least u-v-flow among all (u,v).

If n is the number of vertices in the graph, this simple algorithm would perform $O(n^2)$ iterations of the Maximum flow problem, which can be solved in $O(n^3)$ time. Hence the complexity of the simple algorithm described above is $O(n^5)$ in total.

An improved algorithm will solve the maximum flow problem for every pair (u,v) where u is arbitrarily fixed while v varies over all vertices. This reduces the complexity to $O(n^4)$ and is sound since, if a cut of capacity less than k exists, it is bound to separate u from some other vertex. It can be further improved by Gabow's algorithm that runs in worst case $O(n^3)$ time.

A related problem: finding the minimum k-edge-connected subgraph of G (that is: select as few as possible edges in G that your selection is k-edge-connected) is NP-hard for $k\ge 2$.

See also

• k-vertex-connected graph
• Connectivity (graph theory)
• Matching preclusion
• Menger's theorem
• Robbins theorem

References

43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.