K-vertex-connected graph
Encyclopedia
In graph theory
, a graph G with vertex set V(G) is said to be k-vertex-connected (or k-connected) if the graph remains connected
when you delete fewer than k vertices from the graph. Alternatively, a graph is k-connected if k is the size of the smallest subset of vertices such that the graph becomes disconnected if you delete them.
An equivalent definition for graphs that are not complete
is that a graph is k-connected if any two of its vertices can be joined by k independent paths
; see Menger's theorem
. However, for complete graphs the two definitions differ: the n-vertex complete graph has unbounded connectivity according to the definition based on deleting vertices, but connectivity n − 1 according to the definition based on independent paths, and some authors use alternative definitions according to which its connectivity is n..
A 1-vertex-connected graph is called connected, while a 2-vertex-connected graph is said to be biconnected
.
The vertex-connectivity, or just connectivity, of a graph is the largest k for which the graph is k-vertex-connected.
The 1-skeleton of any k-dimensional convex polytope
forms a k-vertex-connected graph (Balinski's theorem
). As a partial converse, Steinitz's theorem
states that any 3-vertex-connected planar graph
forms the skeleton of a convex polyhedron
.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a graph G with vertex set V(G) is said to be k-vertex-connected (or k-connected) if the graph remains connected
Connectivity (graph theory)
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements which need to be removed to disconnect the remaining nodes from each other. It is closely related to the theory of network flow problems...
when you delete fewer than k vertices from the graph. Alternatively, a graph is k-connected if k is the size of the smallest subset of vertices such that the graph becomes disconnected if you delete them.
An equivalent definition for graphs that are not complete
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
is that a graph is k-connected if any two of its vertices can be joined by k independent paths
Path (graph theory)
In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
; see Menger's theorem
Menger's theorem
In the mathematical discipline of graph theory and related areas, Menger's theorem is a basic result about connectivity in finite undirected graphs. It was proved for edge-connectivity and vertex-connectivity by Karl Menger in 1927...
. However, for complete graphs the two definitions differ: the n-vertex complete graph has unbounded connectivity according to the definition based on deleting vertices, but connectivity n − 1 according to the definition based on independent paths, and some authors use alternative definitions according to which its connectivity is n..
A 1-vertex-connected graph is called connected, while a 2-vertex-connected graph is said to be biconnected
Biconnected graph
In the mathematical discipline of graph theory, a biconnected graph is a connected graph with no articulation vertices.In other words, a biconnected graph is connected and nonseparable, meaning that if any vertex were to be removed, the graph will remain connected.The property of being 2-connected...
.
The vertex-connectivity, or just connectivity, of a graph is the largest k for which the graph is k-vertex-connected.
The 1-skeleton of any k-dimensional convex polytope
Polytope
In elementary geometry, a polytope is a geometric object with flat sides, which exists in any general number of dimensions. A polygon is a polytope in two dimensions, a polyhedron in three dimensions, and so on in higher dimensions...
forms a k-vertex-connected graph (Balinski's theorem
Balinski's theorem
In polyhedral combinatorics, a branch of mathematics, Balinski's theorem is a statement about the graph-theoretic structure of three-dimensional polyhedra and higher-dimensional polytopes...
). As a partial converse, Steinitz's theorem
Steinitz's theorem
In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs...
states that any 3-vertex-connected planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
forms the skeleton of a convex polyhedron
Polyhedron
In elementary geometry a polyhedron is a geometric solid in three dimensions with flat faces and straight edges...
.
See also
- k-edge-connected graphK-edge-connected graphIn graph theory, a graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.-Formal definition:Let G = be an arbitrary graph....
- Connectivity (graph theory)Connectivity (graph theory)In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements which need to be removed to disconnect the remaining nodes from each other. It is closely related to the theory of network flow problems...
- Menger's theoremMenger's theoremIn the mathematical discipline of graph theory and related areas, Menger's theorem is a basic result about connectivity in finite undirected graphs. It was proved for edge-connectivity and vertex-connectivity by Karl Menger in 1927...
- Structural cohesionStructural cohesionStructural cohesion is the sociological conception of cohesion in social groups. It is defined as the minimal number of actors in a social network that need to be removed to disconnect at least two actors in the remaining group. It is thus identical to the question of the node connectivity of a...