TOPICS
Search

k-Connected Graph


A graph G on more than two vertices is said to be k-connected (or k-vertex connected, or k-point connected) if there does not exist a vertex cut of size k-1 whose removal disconnects the graph, i.e., if the vertex connectivity kappa(G)>=k. Therefore, a connected graph on more than one vertex is 1-connected and a biconnected graph on more than two vertices is 2-connected.

The singleton graph is "annoyingly inconsistent" (West 2000, p. 150) since it is connected (specifically, 1-connected), but by convention it is taken to have kappa(K_1)=0.

The wheel graph is the "basic 3-connected graph" (Tutte 1961; Skiena 1990, p. 179).

k-connectedness graph checking is implemented in the Wolfram Language as KVertexConnectedGraphQ[g, k].

The following table gives the numbers of k-connected graphs for n-node graphs (counting the singleton graph K_1 as 1-connected and the path graph P_2 as 2-connected).

kOEISk-connected graphs on 1, 2, ... nodes
1A0013491, 1, 2, 6, 21, 112, 853, 11117, 261080, ...
2A0022180, 1, 1, 3, 10, 56, 468, 7123, 194066, ...
3A0062900, 0, 0, 1, 3, 17, 136, 2388, 80890, ...
4A0862160, 0, 0, 0, 1, 4, 25, 384, 14480, ...
5A0862170, 0, 0, 0, 0, 1, 4, 39, 1051, 102630, 22331311, ...
6A3242400, 0, 0, 0, 0, 0, 1, 5, 59, 3211, 830896, ...
7A3240920, 0, 0, 0, 0, 0, 0, 1, 5, 87, 9940, 7532629, ...

See also

Barnette's Conjecture, Biconnected Graph, Block, Connected Graph, Disconnected Graph, Harary Graph, k-Edge-Connected Graph, Menger's n-Arc Theorem, Polyhedral Graph, Vertex Connectivity, Vertex Cut

Explore with Wolfram|Alpha

References

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 45, 1994.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Sloane, N. J. A. Sequences A000719/M1452, A001349/M1657, A002218/M2873, A006290/M3039, A052442, A052443, A052444, A052445, A086216, A086217, A324240, and A324092 in "The On-Line Encyclopedia of Integer Sequences."Tutte, W. T. "A Theory of 3-Connected Graphs." Indag. Math. 23, 441-455, 1961.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.

Referenced on Wolfram|Alpha

k-Connected Graph

Cite this as:

Weisstein, Eric W. "k-Connected Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/k-ConnectedGraph.html

Subject classifications