K-vertex-connected Graph

Get K-vertex-connected Graph essential facts below. View Videos or join the K-vertex-connected Graph discussion. Add K-vertex-connected Graph to your PopFlock.com topic list for future reference or share this resource on social media.
## Definitions

## Applications

### Polyhedral combinatorics

## Computational complexity

## See also

## Notes

## References

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

K-vertex-connected Graph

In graph theory, a connected graph *G* is said to be ** k-vertex-connected** (or

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

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.

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.

The vertex-connectivity of an input graph *G* can be computed in polynomial time in the following way^{[2]} consider all possible pairs of nonadjacent nodes to disconnect, using Menger's theorem to justify that the minimal-size separator for 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 and with capacity 1 to each edge, noting that a flow of in this graph corresponds, by the integral flow theorem, to pairwise edge-independent paths from to .

*k*-edge-connected graph- Connectivity (graph theory)
- Menger's theorem
- Structural cohesion
- Tutte embedding
- Vertex separator

- ^
^{a}^{b}Schrijver (12 February 2003),*Combinatorial Optimization*, Springer, ISBN 9783540443896 **^***The algorithm design manual*, p 506, and*Computational discrete mathematics: combinatorics and graph theory with Mathematica*, p. 290-291

- 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. - Diestel, Reinhard (2005),
*Graph Theory*(3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4.

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Popular Products

Music Scenes

Popular Artists