# k-context

The **k-connection of** a graph is an important term in graph theory and a generalization of the connection . The k-relationship is clearly a measure of how difficult it is to split a graph into two components by deleting nodes. If the k-connection is large, many nodes must be deleted.

## definition

### Undirected graph

An undirected graph (which is also a multi-graph may be) is *k-fold knot contiguous* (or simply **k times contiguously** or *k-connected* ) when there is no separator in a maximum -element set of nodes and empty edge set there. Equivalent to this is that the subgraph induced by is connected for all node sets with cardinality .

If a subset of the node set has the property that the subgraph induced by is -connected and is not -connected for every node set , then one calls a **k-connected component** of . A 2-connected component is also called a **block** .

The *node connection number* (often referred to as the **connection number** or connection for short ) of a graph is the largest , so that it is connected. An equivalent definition is that the node connection number is the smallest thickness of a separator with an empty set of edges. Graphs k-connected are to have associated numbers , the greater than or equal include .

### Directed graph

A directed graph (which may also include multiple edges) is *k-fold strongly connected* if for each node set of the thickness of the of induced partial graph strongly connected is.

The largest , so that -fold is strongly connected, is called the **strong connected** number and is denoted by.

## example

### K-fold connection

As an example, consider the house of Santa Claus on the right . It is 2-connected, as there are no separators that consist of only one node. Equivalent to this is that there is no articulation . But if you look at z. For example, nodes 3 and 4 separate the house into node sets 5 and 1 and 2, since every path from 5 to 1 or 2 must go through one of nodes 3 or 4. So the house is single and twofold nodal and its nodal number is .

### K-fold strong connection

As an example graph, consider the tournament graph shown on the right . The graph is strongly connected, so in any case simply strongly connected. However, if you start deleting single-element sets of nodes, the strong connection is soon destroyed. If you remove z. B. node 3, node 2 can no longer be reached from node 4. Thus the digraph is simply strongly connected and .

## properties

- Every -connected graph is also -connected (since there is no -element set of nodes that separates, there are of course no -element sets).
- A simple graph is 2-connected if and only if it has no articulation .
- A 1-connected component is exactly the classic connected component .
- If , then applies where is the edge connection number and the minimum degree of the graph . A high correlation therefore requires a high minimum degree. However, the reverse is not true.
- is -contiguous if and only if there are disjoint paths between two nodes . This statement is also known as the global version of Menger's Theorem .

## Algorithms

### Determination of the node connection number

There are polynomial algorithms for calculating the node connection number . One can use flow algorithms for this purpose, for example . For this a maximum - - flow is calculated for all pairs of nodes . According to Menger's theorem, the smallest value that the flow assumes is the node connection number. So if the effort required to determine a - -flow in a graph with n nodes and m edges, then this naive approach yields an effort of . However, there are also more efficient algorithms.

A very good but complicated algorithm for calculating the edge connection of a directed (and thus also undirected) graph with rational weights was developed by H. Gabow (based on the matroid theory, i.e. a set of subtrees).

A lighter algorithm that is also suitable for real weights exists, discovered by Stoer / Wagner and at the same time Nagamotchi / Ibaraki. This works by means of node contraction and only for undirected graphs.

A directed graph algorithm based on flow algorithms was presented by Hao / Orlin.

### Test for k-connection

If one is not interested in the node connection number, but only wants to know whether a graph is k-connected for a given k, then there are fast algorithms. In this way, the 2-relationship can be determined in linear time. For undirected graphs there are linear algorithms that check a 3-relationship. For 4-connection in undirected graphs there are algorithms with effort

## Related terminology

The edge connection is a term similar to the k-connection, except that only separators with an empty set of nodes and an arbitrary set of edges are considered. The edge connection is a measure of how many edges have to be removed from a graph so that it breaks down into different components. A term for directed graphs that is analogous to the edge connection is formed by the arc connection , which considers directed edges instead of undirected edges.

## Number of simple non-isomorphic unnamed graphs

Number of different non-isomorphic simple unnamed - connected graphs with nodes for from 1 to 9, including the reference OEIS (simple graphs include both connected and non-connected):

\ | 1 | 2 | 3 | 4th | 5 | 6th | 7th | 8th | 9 | OEIS |
---|---|---|---|---|---|---|---|---|---|---|

easy | 1 | 2 | 4th | 11 | 34 | 156 | 1044 | 12346 | 274668 | A000088 |

1 | 1 | 1 | 2 | 6th | 21st | 112 | 853 | 11117 | 261080 | A001349 |

2 | 0 | 1 | 1 | 3 | 10 | 56 | 468 | 7123 | 194066 | A002218 |

3 | 0 | 0 | 1 | 1 | 3 | 17th | 136 | 2388 | 80890 | A006290 |

4th | 0 | 0 | 0 | 1 | 1 | 4th | 25th | 384 | 14480 | A086216 |

5 | 0 | 0 | 0 | 0 | 1 | 1 | 4th | 39 | 1051 | A086217 |

6th | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 5 | 59 | |

7th | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 5 |

Number of different non-isomorphic simple unnamed graphs with nodes and the node connection number :

\ | 1 | 2 | 3 | 4th | 5 | 6th | 7th | 8th | 9 | OEIS |
---|---|---|---|---|---|---|---|---|---|---|

0 | 0 | 1 | 2 | 5 | 13 | 44 | 191 | 1229 | 13588 | |

1 | 1 | 0 | 1 | 3 | 11 | 56 | 385 | 3994 | 67014 | A052442 |

2 | 0 | 1 | 0 | 2 | 7th | 39 | 332 | 4735 | 113176 | A052443 |

3 | 0 | 0 | 1 | 0 | 2 | 13 | 111 | 2004 | 66410 | A052444 |

4th | 0 | 0 | 0 | 1 | 0 | 3 | 21st | 345 | 13429 | A052445 |

5 | 0 | 0 | 0 | 0 | 1 | 0 | 3 | 34 | 992 | |

6th | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 4th | 54 |

## literature

- Reinhard Diestel: graph theory . Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 pages).
- 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).