endblocking

Endblocking, in graph theory, refers to a block of a connected graph that contains exactly one cut-vertex of the graph. A block is a maximal subgraph with no cut-vertex of the subgraph, and a cut-vertex (articulation point) is a vertex whose removal increases the number of connected components of the graph. An end-block is thus a block that attaches to the remainder of the graph through a single vertex, or equivalently, a terminal block in the block–cut tree.

The block–cut tree is a bipartite representation whose nodes correspond to blocks and to articulation points, with edges connecting a block to every cut-vertex it contains. In this tree, end-blocks appear as leaves. This perspective emphasizes that end-blocks are the components at the “ends” of the decomposition, and that removing their single shared vertex separates the block from the rest of the graph.

End-blocks provide a useful tool for structural analysis and inductive proofs. They allow properties of the whole graph to be studied by examining its end-blocks and the articulation points through which they connect to the remainder of the graph. Endblocking is particularly relevant in algorithms that decompose graphs, such as those computing connectivity, planarity-related properties, or in proofs that proceed by successive removal of end-blocks.

In practice, a graph with no cut-vertices has no end-blocks; when a graph contains multiple blocks, the leaf blocks of the block–cut tree are the end-blocks. See also articulation points, block graphs, and block–cut trees.