Biconnected graph

From Wikipedia, the free encyclopedia

You have new messages (last change).

In the mathematical discipline of graph theory, a biconnected graph is a connected graph with no articulation vertices.

In other words, a biconnected graph is nonseparable, meaning if any edge were to be removed, the graph will remain connected.

Biconnected is another way of saying the graph is a K-vertex-connected graph, where K = 2.

This property is especially useful in maintaining a graph with a two-fold redundancy, to prevent disconnection upon the removal of a single edge (or connection).

The use of biconnected graphs is very important in the field of networking (see Network flow), because of this property of redundancy.

[edit] Definition

A biconnected graph is a connected graph that is not broken into disconnected pieces by deleting any single vertex (and incident edges).

A biconnected undirected graph G is a set of vertices V so that every vertex has at least two connecting edges (an adjacency list of at least size two), connecting to separate vertices other than itself. A biconnected graph is a biconnected component.

A biconnected strongly connected directed graph G is a set of vertices V so that every vertex has at least two in-degree vertices, and at least two out-degree vertices; ie. there are at least two independent paths from any vertex to any other vertex.

Sloan's A002218 A002218

Nonseparable (or 2-connected) graphs (or blocks) with n nodes
Vertices Number of Possibilities
1 0
2 1
3 1
4 3
5 10
6 56
7 468
8 7123
9 194066
10 9743542
11 900969091
12 153620333545
13 48432939150704
14 28361824488394169
15 30995890806033380784
16 63501635429109597504951
17 244852079292073376010411280
18 1783160594069429925952824734641
19 24603887051350945867492816663958981

[edit] Examples

[edit] References

Retrieved from "http://en.wikipedia.org../../../b/i/c/Biconnected_graph.html"