Characterizing block graphs in terms of their vertex-induced partitions

A Dress, Katharina Huber, Jack Koolen, Vincent Moulton, Andreas Spillner

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)
3 Downloads (Pure)

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 languageEnglish
Pages (from-to)1-9
Number of pages9
JournalAustralasian Journal of Combinatorics
Volume66
Issue number1
Publication statusPublished - 1 Aug 2016

Keywords

  • block graph
  • vertex-induced partition
  • phylogenetic combinatorics
  • compatible decompositions
  • strongly compatible decomposition

Cite this