# 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 . ${\ displaystyle G = (V, E)}$ ${\ displaystyle T = (X, Y)}$${\ displaystyle G}$${\ displaystyle (k-1)}$${\ displaystyle X}$${\ displaystyle Y = \ emptyset}$${\ displaystyle K}$${\ displaystyle k-1}$${\ displaystyle V \ backslash K}$

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 . ${\ displaystyle U}$${\ displaystyle V}$${\ displaystyle U}$ ${\ displaystyle G [U]}$ ${\ displaystyle k}$${\ displaystyle G [W]}$${\ displaystyle W \ supset U, W \ neq U}$${\ displaystyle k}$${\ displaystyle G [U]}$${\ displaystyle G}$

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 . ${\ displaystyle \ kappa (G)}$${\ displaystyle G}$${\ displaystyle k}$${\ displaystyle G}$ ${\ displaystyle k}$${\ displaystyle G}$${\ displaystyle \ kappa (G)}$${\ displaystyle k}$${\ displaystyle \ kappa (G) \ geq k}$

### 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. ${\ displaystyle D = (V, A)}$${\ displaystyle U}$${\ displaystyle k-1}$${\ displaystyle V \ backslash U}$ ${\ displaystyle G \ left [V \ backslash U \ right]}$

The largest , so that -fold is strongly connected, is called the strong connected number and is denoted by. ${\ displaystyle k}$${\ displaystyle D}$ ${\ displaystyle k}$${\ displaystyle \ sigma (D)}$

## 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 . ${\ displaystyle \ kappa (G) = 2}$

### K-fold strong connection

The digraph treated in the example

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 . ${\ displaystyle \ sigma (D) = 1}$

## properties

• Every -connected graph is also -connected (since there is no -element set of nodes that separates, there are of course no -element sets).${\ displaystyle k}$${\ displaystyle (k-1)}$${\ displaystyle (k-1)}$${\ displaystyle G}$${\ displaystyle (k-2)}$
• 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.${\ displaystyle | G | \ geq 2}$${\ displaystyle \ delta (G) \ geq \ lambda (G) \ geq \ kappa (G)}$${\ displaystyle \ lambda (G)}$${\ displaystyle \ delta (G)}$${\ displaystyle G}$
• ${\ displaystyle G}$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 .${\ displaystyle k}$${\ displaystyle G}$${\ displaystyle k}$

## 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. ${\ displaystyle s, t}$${\ displaystyle s}$${\ displaystyle t}$${\ displaystyle F (n, m)}$${\ displaystyle s}$${\ displaystyle t}$${\ displaystyle {\ mathcal {O}} (n ^ {2} F (n, m))}$

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${\ displaystyle {\ mathcal {O}} (n ^ {2})}$

## 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): ${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle n}$

${\ displaystyle k}$ \ ${\ displaystyle n}$ 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 : ${\ displaystyle n}$${\ displaystyle \ kappa}$

${\ displaystyle \ kappa}$ \ ${\ displaystyle n}$ 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