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.
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.[citation needed]
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). This definition produces the same answer, n − 1, for the connectivity of the complete graph Kn.[1] Clearly the complete graph with n vertices has connectivity n − 1 under this definition.
A 1-connected graph is called connected; a 2-connected graph is called biconnected. A 3-connected graph is called triconnected.
Applications
Components
Every graph decomposes into a tree of 1-connected components. 1-connected graphs decompose into a tree of biconnected components. 2-connected graphs decompose into a tree of triconnected components.
Polyhedral combinatorics
The 1-skeleton of any k-dimensional convex polytope forms a k-vertex-connected graph (Balinski's theorem).[2] 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[3] consider all possible pairs [math]\displaystyle{ (s, t) }[/math] of nonadjacent nodes to disconnect, using Menger's theorem to justify that the minimal-size separator for [math]\displaystyle{ (s, t) }[/math] 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 [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math] with capacity 1 to each edge, noting that a flow of [math]\displaystyle{ k }[/math] in this graph corresponds, by the integral flow theorem, to [math]\displaystyle{ k }[/math] pairwise edge-independent paths from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math].
See also
- k-edge-connected graph
- Connectivity (graph theory)
- Menger's theorem
- Structural cohesion
- Tutte embedding
- Vertex separator
Notes
- ↑ 1.0 1.1 Schrijver (12 February 2003), Combinatorial Optimization, Springer, ISBN 9783540443896, https://books.google.com/books?id=mqGeSQ6dJycC&q=%22k-vertex-connected+%22
- ↑ 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.
- ↑ The algorithm design manual, p 506, and Computational discrete mathematics: combinatorics and graph theory with Mathematica, p. 290-291
References
- Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4, http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/.
 |  |
