Articulation Vertex

An articulation vertex of a connected graph, also called a cut-vertex (Harary 1994, p. 26; West 2000; Gross and Yellen 2006) or "cutpoint" (Harary 1994, p. 26), is a vertex whose removal will disconnect the graph (Chartrand 1985). More generally, an articulation vertex of a not-necessarily-connected graph is a vertex whose removal increases the connected component count (Harary 1994, p. 26; West 2000, p. 23). An example graph due to West (2000, pp. 22-23) is illustrated above with its articulation vertices  and  indicated.

A graph on two or more vertices possessing no articulation vertices is called a biconnected graph. A vertex is an articulation vertex iff it appears in two biconnected components.

A maximal connected subgraph of a given graph  that has no articulation vertex is called a block (West 2000, p. 155).

The endpoints of a graph bridge are articulation vertices unless they both have vertex degree 1. On the other hand, it is possible for a non-bridge edge to have both endpoints be articulation vertices.

The Wolfram Language function FindVertexCut[g] returns a vertex cut set of smallest size for a connected graph , which corresponds to an articulation vertex if the set is of size 1.

The analog of an articulation vertex for edges is called a graph bridge.

---

REFERENCES

Chartrand, G. "Cut-Vertices and Bridges." §2.4 in Introductory Graph Theory. New York: Dover, pp. 45-49, 1985.

Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, 2006.

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 175, 1990.

West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength