Blocks and cut vertices of the Buneman graph

A. W. M. Dress, K. T. Huber, J. Koolen, V. Moulton

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


Given a set $\Sigma$ of bipartitions of some finite set $X$ of cardinality at least $2$, one can associate to $\Sigma$ a canonical $X$-labeled graph $\mathcal{B}(\Sigma)$, called the Buneman graph. This graph has several interesting mathematical properties—for example, it is a median network and therefore an isometric subgraph of a hypercube. It is commonly used as a tool in studies of DNA sequences gathered from populations. In this paper, we present some results concerning the cut vertices of $\mathcal{B}(\Sigma)$, i.e., vertices whose removal disconnect the graph, as well as its blocks or $2$-connected components—results that yield, in particular, an intriguing generalization of the well-known fact that $\mathcal{B}(\Sigma)$ is a tree if and only if any two splits in $\Sigma$ are compatible
Original languageEnglish
Pages (from-to)1902-1919
Number of pages18
JournalSIAM Journal on Discrete Mathematics
Issue number4
Publication statusPublished - Dec 2011

Cite this