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,
(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 [g]. Precomputed vertex connectivities are available for many named graphs via [graph, ].
See also
Biconnected Graph, Connected Graph, Disconnected Graph, Edge Connectivity, k-Connected Graph, Menger's n-Arc Theorem, Vertex CutExplore with Wolfram|Alpha
More things to try:
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 ConnectivityCite this as:
Weisstein, Eric W. "Vertex Connectivity." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/VertexConnectivity.html