k-vertex-connected graph

In graph theory, a connected graph G is said to be k-vertex-connected (or k-connected) if it has more than k vertices and remains connected whenever fewer than k vertices are removed.

A graph with connectivity 4.

The vertex-connectivity, or just connectivity, of a graph is the largest k for which the graph is k-vertex-connected.

Definitions

A graph (other than a complete graph) has connectivity k if k is the size of the smallest subset of vertices such that the graph becomes disconnected if you delete them.[1] Complete graphs are not included in this version of the definition since they cannot be disconnected by deleting vertices. The complete graph with n vertices has connectivity n − 1, as implied by the first definition.

An equivalent definition is that a graph with at least two vertices is k-connected if, for every pair of its vertices, it is possible to find k vertex-independent paths connecting these vertices; see Menger's theorem (Diestel 2005, p. 55). This definition produces the same answer, n − 1, for the connectivity of the complete graph K_n.[1]

A 1-connected graph is called connected; a 2-connected graph is called biconnected. A 3-connected graph is called triconnected.

Applications

Polyhedral combinatorics

The 1-skeleton of any k-dimensional convex polytope forms a k-vertex-connected graph (Balinski's theorem, Balinski 1961). As a partial converse, Steinitz's theorem states that any 3-vertex-connected planar graph forms the skeleton of a convex polyhedron.

Computational complexity

The vertex-connectivity of an input graph G can be computed in polynomial time in the following way[2] consider all possible pairs $(s,t)$ of nonadjacent nodes to disconnect, using Menger's theorem to justify that the minimal-size separator for $(s,t)$ is the number of pairwise vertex-independent paths between them, encode the input by doubling each vertex as an edge to reduce to a computation of the number of pairwise edge-independent paths, and compute the maximum number of such paths by computing the maximum flow in the graph between $s$ and $t$ with capacity 1 to each edge, noting that a flow of $k$ in this graph corresponds, by the integral flow theorem, to $k$ pairwise edge-independent paths from $s$ to $t$ .

gollark: Well, gender is actually gaseous and can spread across borders easily. They're calling for hermetic seals across borders to prevent this.

gollark: The opinions of "Jesus", current occupant of Site 2-Alpha's containment cells, are not relevant.

gollark: https://github.com/osmarks/website

gollark: kit: yes, my website is partly compiled using a horrible JS program.

gollark: If you have gender, you can ignore national border control.

Notes

Schrijver, Combinatorial Optimization, Springer
The algorithm design manual, p 506, and Computational discrete mathematics: combinatorics and graph theory with Mathematica, p. 290-291

References

Balinski, M. L. (1961), "On the graph structure of convex polyhedra in n-space", Pacific Journal of Mathematics, 11 (2): 431–434, doi:10.2140/pjm.1961.11.431, archived from the original on 2012-09-11.
Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[Schrijver-1] Schrijver, Combinatorial Optimization, Springer

[2] The algorithm design manual, p 506, and Computational discrete mathematics: combinatorics and graph theory with Mathematica, p. 290-291