k-Connected Graph
المؤلف:
Harary, F
المصدر:
Graph Theory. Reading, MA: Addison-Wesley
الجزء والصفحة:
...
8-3-2022
2629
k-Connected Graph
A graph 
on more than two vertices is said to be 
-connected (or 
-vertex connected, or 
-point connected) if there does not exist a vertex cut of size 
whose removal disconnects the graph, i.e., if the vertex connectivity 
. 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 
.
The wheel graph is the "basic 3-connected graph" (Tutte 1961; Skiena 1990, p. 179).
-connectedness graph checking is implemented in the Wolfram Language as KVertexConnectedGraphQ[g, k].
The following table gives the numbers of 
-connected graphs for 
-node graphs (counting the singleton graph 
as 1-connected and the path graph 
as 2-connected).
 |
OEIS |
 -connected graphs on 1, 2, ... nodes |
| 1 |
A001349 |
1, 1, 2, 6, 21, 112, 853, 11117, 261080, ... |
| 2 |
A002218 |
0, 1, 1, 3, 10, 56, 468, 7123, 194066, ... |
| 3 |
A006290 |
0, 0, 0, 1, 3, 17, 136, 2388, 80890, ... |
| 4 |
A086216 |
0, 0, 0, 0, 1, 4, 25, 384, 14480, ... |
| 5 |
A086217 |
0, 0, 0, 0, 0, 1, 4, 39, 1051, 102630, 22331311, ... |
| 6 |
A324240 |
0, 0, 0, 0, 0, 0, 1, 5, 59, 3211, 830896, ... |
| 7 |
A324092 |
0, 0, 0, 0, 0, 0, 0, 1, 5, 87, 9940, 7532629, ...
|
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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
