Blocks and Cut Vertices of the Buneman Graph

Details Blocks and Cut Vertices of the Buneman Graph Blocks and Cut Vertices of the Buneman Graph

2011-01-25

arxiv.org/abs/1101.4927v1

Mathematics

Combinatorics

Scientific paper

Given a set $\Sg$ of bipartitions of some finite set $X$ of cardinality at least 2, one can associate to $\Sg$ a canonical $X$-labeled graph $\B(\Sg)$, 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 {\em cut vertices} of $\B(\Sg)$, i.e., vertices whose removal disconnect the graph, as well as its {\em blocks} or 2-{\em connected components} - results that yield, in particular, an intriguing generalization of the well-known fact that $\B(\Sg)$ is a tree if and only if any two splits in $\Sg$ are compatible.

Affiliated with

Also associated with

No associations

Rating

Blocks and Cut Vertices of the Buneman Graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Blocks and Cut Vertices of the Buneman Graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Blocks and Cut Vertices of the Buneman Graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-418134