BLOCKS AND CUT VERTICES OF THE BUNEMAN GRAPH
SCIE
SCOPUS
- Title
- BLOCKS AND CUT VERTICES OF THE BUNEMAN GRAPH
- Authors
- Dress, AWM; Huber, KT; Koolen, J; Moulton, V
- Date Issued
- 2011-12
- Publisher
- SIAM
- 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 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 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 B(Sigma) is a tree if and only if any two splits in Sigma are compatible.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/12923
- DOI
- 10.1137/090764360
- ISSN
- 0895-4801
- Article Type
- Article
- Citation
- SIAM JOURNAL ON DISCRETE MATHEMATICS, vol. 25, no. 4, page. 1902 - 1919, 2011-12
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.