Characterizing block graphs in terms of their vertex-induced partitions

Block graphs are a generalization of trees that arise in areas such as metric graph theory, molecular graphs, and phylogenetics. Given a finite connected simple graph G = (V, E) with vertex set V and edge set E subset of ((V)(2)), we will show that the (necessarily unique) smallest block graph with vertex set V whose edge set contains E is uniquely determined by the V-indexed family P-G = (pi(v) )(nu is an element of V) of the partitions pi(v) of the set V into the set of connected components of the graph (V, {e is an element of E : v is not an element of e}). Moreover, we show that an arbitrary V-indexed family P = (p(v))(v is an element of V) of partitions p(v) of the set V is of the form P = P-G for some connected simple graph G = (V, E) with vertex set V as above if and only if, for any two distinct elements u, v is an element of V, the union of the set in pv that contains u and the set in p(u) that contains v coincides with the set V, and {v} is an element of p(v) holds for all v is an element of V. As well as being of inherent interest to the theory of block graphs, these facts are also useful in the analysis of compatible decompositions of finite metric spaces.