Block

 

A block is a maximal connected subgraph of a given graph  that has no articulation vertex (West 2000, p. 155). If a block has more than two vertices, then it is biconnected. The blocks of a loopless graph are its isolated points, bridges, and maximal 2-connected subgraphs (West 2000, p. 155; Gross and Yellen 2006, p. 241). Examples of graphs with their corresponding blocks due to Harary (1994, p. 26) and West (2000, p. 155) are illustrated above.

If a graph  is connected and has no articulation vertices, then  itself is called a block (Harary 1994, p. 26; West 2000, p. 155).

Blocks arise in graph theoretical problems such as finding unit-distance graphs and the graph genus of connected graphs. For example, a connected graph is unit-distance if and only if each of its blocks is unit-distance and the graph coarseness of a graph is the sum of the coarsenesses of its blocks.

---

REFERENCES

Aho, A. V.; Hopcroft, J. E.; and Ullman, J. D. The Design and Analysis of Computer Algorithms. Reading, MA: Addison-Wesley, 1974.

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. "Biconnected Components." §5.1.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 175-177, 1990.

West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 155-158, 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