Blocks and Cut Vertices of the Buneman Graph
Dress, AWM, Huber, KT, 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 |
Related URLs: | |
Depositing User: | Rhiannon Harvey |
Date Deposited: | 09 Jan 2012 10:25 |
Last Modified: | 08 Jun 2022 14:30 |
URI: | https://ueaeprints.uea.ac.uk/id/eprint/35935 |
DOI: | 10.1137/090764360 |
Actions (login required)
![]() |
View Item |