TOPICS
Search

Biconnected Graph


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 G having vertex connectivity kappa(G)>=2.

BiconnectedGraphs

The numbers of biconnected simple graphs on n=1, 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.

NotBiconnectedGraph

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 n=1, 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] >1. 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.


See also

Articulation Vertex, Block, Connected Graph, k-Connected Graph

Explore with Wolfram|Alpha

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."

Referenced on Wolfram|Alpha

Biconnected Graph

Cite this as:

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

Subject classifications