Quick Reference

1 of a computer network. A rather loosely defined property referring either to the extent to which sites wishing to connect to the network are actually equipped with a network connection, or to the extent to which sites with an existing connection are still able to contact other network sites in the event of a component failure.

2 of a graph G. The minimum number of vertices (and associated edges) of G whose removal from G results either in a graph that is no longer connected or in a trivial graph with a single vertex: at least k vertices must be removed from a graph with k-connectivity. The higher the connectivity the more edges there are joining vertices.

The quantity described above is sometimes called the vertex connectivity to distinguish it from the edge connectivity, which by analogy is the minimum number of edges whose removal from G results in a graph that is disconnected or trivial.

Subjects: Computing.

Reference entries