Characterizing Block Graphs in Terms of their Vertex-Induced Partitions

Abstract

Given a finite connected simple graph $G=(V,E)$ with vertex set $V$ and edge set $E\subseteq \left(\genfrac{}{}{0ex}{}{V}{2}\right)$, we will show that $1.$ the (necessarily unique) smallest block graph with vertex set $V$ whose edge set contains $E$ is uniquely determined by the $V$-indexed family ${\mathbf{P}}_G:=({\pi }_0(G^{(v)}){)}_{v\in V}$ of the various partitions ${\pi }_0(G^{(v)})$ of the set $V$ into the set of connected components of the graph $G^{(v)}:=(V,\{e\in E:v\notin e\})$, $2.$ the edge set of this block graph coincides with set of all $2$-subsets $\{u,v\}$ of $V$ for which $u$ and $v$ are, for all $w\in V-\{u,v\}$, contained in the same connected component of $G^{(w)}$, $3.$ and an arbitrary $V$-indexed family $\mathbf{P}p=({\mathbf{p}}_v{)}_{v\in V}$ of partitions ${\pi }_v$ of the set $V$ is of the form $\mathbf{P}p=\mathbf{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\in V$, the union of the set in ${\mathbf{p}}_v$ that contains $u$ and the set in ${\mathbf{p}}_u$ that contains $v$ coincides with the set $V$, and $\{v\}\in {\mathbf{p}}_v$ holds for all $v\in 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 and block realizations of finite metric spaces.