TOPICS
Search

Block

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
Blocks

A block is a maximal connected subgraph of a given graph G 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 G is connected and has no articulation vertices, then G 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.

See also

Articulation Vertex, Biconnected Graph, Block Design, Digit Block, k-Connected Graph, Square Polyomino

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Block

Cite this as:

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

Subject classifications