Abstract
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\subseteq \binom{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 $\Pp_G =\big(\pi_v)_{v \in V}$ of the partitions $\pi_v$ of the set $V$ into the set of connected components of the graph $(V,\{e\in E: v\notin e\})$. Moreover, we show that an arbitrary $V$indexed family $\Pp=(\p_v)_{v \in V}$ of partitions $\p_v$ of the set $V$ is of the form $\Pp=\Pp_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 $\p_v$ that contains $u$ and the set in $\p_u$ that contains $v$ coincides with the set $V$, and $\{v\}\in \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 of finite metric spaces.
Original language  English 

Pages (fromto)  19 
Number of pages  9 
Journal  Australasian Journal of Combinatorics 
Volume  66 
Issue number  1 
Publication status  Published  1 Aug 2016 
Keywords
 block graph
 vertexinduced partition
 phylogenetic combinatorics
 compatible decompositions
 strongly compatible decomposition
Profiles

Katharina Huber
 School of Computing Sciences  Associate Professor
 Computational Biology  Member
Person: Research Group Member, Academic, Teaching & Research

Vincent Moulton
 School of Computing Sciences  Professor in Computational Biology
 Computational Biology  Member
Person: Research Group Member, Academic, Teaching & Research