Block-cutvertex trees and block-cutvertex partitions (Q1849911)

The graph whose vertices are the blocks and cutvertices of a connected graph \(G\), and whose edges join the cutvertices with those blocks to which they belong is called the block-cutvertex graph of \(G\). Some other authors showed that a graph \(H\) is the block-cutvertex graph of a graph if and only if \(H\) is a tree in which the distance between any two leaves is even. The concept of a block-cutvertex partition of a tree \(T\) is introduced in this article (it is a collection \(\{T_1,\dots, T_k\}\) of block-cutvertex trees such that each \(T_i\) is a subtree of \(T\) and each edge of \(T\) is in exactly one \(T_i\)). The author proves that a tree has such a partition if and only if it does not have a perfect matching. He presents various concepts and algorithms related to block-cutvertex partitions.