Vertex Connectivity

The vertex connectivity  of a graph , also called "point connectivity" or simply "connectivity," is the minimum size of a vertex cut, i.e., a vertex subset  such that  is disconnected or has only one vertex.

Because complete graphs  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  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 , "is annoyingly inconsistent" since it is connected, but for consistency in discussing connectivity, it is considered to have . The path graph  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 .

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

Let  be the edge connectivity of a graph  and  its minimum degree, then for any graph,

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

For a connected strongly regular graph or distance-regular graph with vertex degree ,  (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"].

REFERENCES

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 43, 1994.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 178-179, 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.