Read More
Date: 22-7-2016
1262
Date: 27-4-2022
2503
Date: 19-5-2022
1107
|
A biconnected graph is a connected graph having no articulation vertices (Skiena 1990, p. 175). An equivalent definition for graphs on more than two vertices is a graph having vertex connectivity .
The numbers of biconnected simple graphs on , 2, ... nodes are 0, 0, 1, 3, 10, 56, 468, ... (cf. OEIS A002218). The first few of these are illustrated above.
Maximal connected graphs on two or more vertices are called blocks or nonseparable graphs (cf. Harary 1994, p. 26). Biconnected graphs are closely related to blocks. If a block has more than two vertices, then it is biconnected (West 2000, p. 155). Conversely, biconnected graphs on two or more vertices are blocks.
A number of graphs that are connected but not biconnected are illustrated above. Such graphs are called 1-connected, and the numbers of such graphs for , 2, ... are given by 1, 1, 1, 3, 11, 56, 385, ... (OEIS A052442).
A graph can be tested for biconnectivity in the Wolfram Language using KVertexConnectedGraphQ[g, 2] or VertexConnectivity[g] . A collection of biconnected graphs is available using GraphData["Biconnected].
Any graph containing a node of degree 1 cannot be biconnected. All Hamiltonian graphs are biconnected (Skiena 1990, p. 177), but the converse is not necessarily so. In particular, a non-biconnected graph is automatically non-Hamiltonian, which can be seen be noting that if removal of an articulation vertex left a Hamiltonian path, this would imply that disconnected graphs were connected. The following table summarizes some named graphs that are biconnected but non-Hamiltonian.
graph |
|
theta-0 graph | 7 |
Petersen graph | 10 |
Herschel graph | 11 |
first Blanuša snark | 18 |
second Blanuša snark | 18 |
flower snark | 20 |
Coxeter graph | 28 |
double star snark | 30 |
Thomassen graph | 34 |
Tutte's graph | 46 |
Szekeres snark | 50 |
Meredith graph | 70 |
REFERENCES
Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.
Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.
Sloane, N. J. A. Sequences A002218/M2873 and A052442 in "The On-Line Encyclopedia of Integer Sequences."
|
|
دراسة يابانية لتقليل مخاطر أمراض المواليد منخفضي الوزن
|
|
|
|
|
اكتشاف أكبر مرجان في العالم قبالة سواحل جزر سليمان
|
|
|
|
|
المجمع العلمي ينظّم ندوة حوارية حول مفهوم العولمة الرقمية في بابل
|
|
|