Blocks and cut vertices of the Buneman graph

Dress, A. W. M., Huber, K. T., Koolen, J. and Moulton, V. (2011) Blocks and cut vertices of the Buneman graph. SIAM Journal on Discrete Mathematics, 25 (4). pp. 1902-1919.

Full text not available from this repository. (Request a copy)

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

Item Type:	Article
Faculty \ School:	Faculty of Science > School of Computing Sciences
UEA Research Groups:	Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018) Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre Faculty of Science > Research Groups > Computational Biology > Computational biology of RNA (former - to 2018)
Depositing User:	Rhiannon Harvey
Date Deposited:	09 Jan 2012 10:25
Last Modified:	13 Apr 2025 06:30
URI:	https://ueaeprints.uea.ac.uk/id/eprint/35935
DOI:	10.1137/090764360

Actions (login required)

View Item