Arc connection

The arc connection is a basic concept of graph theory and a generalization of the connection for directed graphs (digraphs). The arc connection is a measure of how difficult it is to split a digraph into two or more components by deleting directed edges . If the arc connection is large, many directed edges must be removed.

definition

A directed graph , the strongly connected is called k-fold arc contiguous or k-arc-contiguous when the graph for all edge quantities of cardinality is strongly connected. ${\ displaystyle D = (V, A)}$ ${\ displaystyle D ': = (V, A \ setminus U)}$ ${\ displaystyle U}$ ${\ displaystyle k-1}$

The largest , so that k-times is arc -related, is called the arc-connection number and is denoted by. ${\ displaystyle k}$ ${\ displaystyle D}$ ${\ displaystyle \ lambda (D)}$

If trivial or not strongly connected, it is called 0-fold arc-connected and is set ${\ displaystyle D}$ ${\ displaystyle \ lambda (D) = 0}$

example

The example graph is a tournament graph

As an example, consider the directed graph on the right. This is not trivial and strongly connected, so the graph is definitely 1-arc connected. If you start to delete single-element sets of edges (e.g. the edge ), the strong connection is destroyed (after the edge has been deleted, node 1 can no longer be reached from node 4). Thus the graph is not 2-arc-connected and it is because the graph is 0-arc-connected and 1-arc-connected. ${\ displaystyle (4,3)}$ ${\ displaystyle \ lambda (D) = 1}$

Algorithms

There are polynomial algorithms to determine the arc connection number . One can use flow algorithms for this purpose, for example . If the effort is to determine a minimal cut in the graph, then this naive approach has an effort of . There are much more efficient, but also more complicated algorithms. ${\ displaystyle F (n, m)}$ ${\ displaystyle {\ mathcal {O}} (nF (n, m))}$

Related terminology

An analog of the arc connection for undirected graphs is the edge connection . Here undirected edges are removed until the graph breaks down into its connected components. There is also the concept of the k-connection , which is a measure of how many vertices have to be removed from a graph so that it breaks down into its components.

literature

Lutz Volkmann: Fundamente der Graphentheorie , Springer (Vienna) 1996, ISBN 3-211-82774-9 ( newer, online version "Graphs on all corners and edges" ; PDF; 3.7 MB)
Alexander Schrijver : Combinatorial optimization . polyhedra and efficiency. Springer, Berlin 2003, ISBN 978-3-540-44389-6 (3 volumes, 1881 pages).