The (vertex) connectivity is the minimum number of vertices (aka nodes) you have to remove to either make the graph no longer connected, or reduce it to a single vertex (node). is said to be -(vertex)-connected for any . Note that “removing a vertex” in graph theory also involves removing all the edges incident to that vertex.
The edge connectivity of a graph is more straightforward, it is just the minimum number of edges you have to remove to make the graph no longer connected. is said to be -edge-connected for any . And note “removing an edge” is simply that; it does not entail removing any vertices.
If the graph contains at least one bridge. If (the graph is 2-edge-connected) every edge is part of a cycle (circuit, closed path).
If the graph contains at least one cutvertex. If (the graph is 2-vertex-connected) there is, for any pair of vertices, a cycle they both lie on.
For the complete graphs we have .
For any graph we have where the latter is the minimum valency in (the valency of a vertex is the number of edges sprouting from it).
For directed graphs there are two notions of connectivity (http://planetmath.org/ConnectedGraph) (“weak” if the underlying graph is connected, “strong” if you can get from everywhere to everywhere).
There are now pictures (http://planetmath.org/ExamplesOfKConnectedGraphs) to go with this entry.
|Date of creation||2013-03-22 13:10:58|
|Last modified on||2013-03-22 13:10:58|
|Last modified by||marijke (8873)|
|Defines||-connected -vertex-connected -edge-connected connectivity|