BLOCKS AND CUT VERTICES OF THE BUNEMAN GRAPH

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.