Blocks and Cut Vertices of the Buneman Graph

AWM Dress, KT Huber, J Koolen, V Moulton

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

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
Volume25
Issue number4
DOIs
Publication statusPublished - Dec 2011

Cite this