Blocks and cut vertices of the Buneman graph

Dress, A. W. M., Huber, K. T., Koolen, J. and Moulton, V. ORCID: https://orcid.org/0000-0001-9371-6435 (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:	15 Jun 2023 08:31
URI:	https://ueaeprints.uea.ac.uk/id/eprint/35935
DOI:	10.1137/090764360

Actions (login required)

View Item