TOPICS
Search

Vertex Connectivity


The vertex connectivity kappa(G) of a graph G, also called "point connectivity" or simply "connectivity," is the minimum size of a vertex cut, i.e., a vertex subset S subset= V(G) such that G-S is disconnected or has only one vertex.

Because complete graphs K_n have no vertex cuts (i.e., there is no subset of vertices whose removal disconnects them), a convention is needed to assign them a vertex connectivity. The convention of letting kappa(K_n)=n-1 allows most general results about connectivity to remain valid on complete graphs (West 2001, p. 149). Though as noted by West (2001, p. 150), the singleton graph K_1, "is annoyingly inconsistent" since it is connected, but for consistency in discussing connectivity, it is considered to have kappa(K_1)=0. The path graph P_2 is also problematic, since it has no articulation vertices and for the purpose of theorems such as those involving unit-distance graphs, it is convenient to regard it as biconnected, yet it has vertex connectivity of kappa(P_2)=1.

A graph G with kappa(G)>=1 or on a single vertex is said to be connected, a graph with kappa(G)>=2 is said to be biconnected (as well as connected), and in general, a graph with vertex connectivity >=k is said to be k-connected. For example, the utility graph K_(3,3) has vertex connectivity kappa(K_(3,3))=3, so it is 1-, 2-, and 3-connected, but not 4-connected.

The vertex connectivity of a graph can be computed in polynomial time (Skiena 1990, p. 506; Pemmaraju and Skiena 2003, pp. 290-291).

Let lambda(G) be the edge connectivity of a graph G and delta(G) its minimum degree, then for any graph,

 kappa(G)<=lambda(G)<=delta(G)

(Whitney 1932, Harary 1994, p. 43).

For a connected strongly regular graph or distance-regular graph with vertex degree k, kappa=k (A. E. Brouwer, pers. comm., Dec. 17, 2012).

The vertex connectivity of a graph can be determined in the Wolfram Language using VertexConnectivity[g]. Precomputed vertex connectivities are available for many named graphs via GraphData[graph, "VertexConnecitivity"].


See also

Biconnected Graph, Connected Graph, Disconnected Graph, Edge Connectivity, k-Connected Graph, Menger's n-Arc Theorem, Vertex Cut

Explore with Wolfram|Alpha

References

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 43, 1994.Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, 2003.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.Whitney, H. "Congruent Graphs and the Connectivity of Graphs." Amer. J. Math. 54, 150-168, 1932.

Referenced on Wolfram|Alpha

Vertex Connectivity

Cite this as:

Weisstein, Eric W. "Vertex Connectivity." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/VertexConnectivity.html

Subject classifications