The Abstract

	Annals of Combinatorics 1 (1997) 329-337 On the Number of Vertices and Edges of the Buneman Graph A. Dress¹, M. Hendy², K. Huber¹, and V. Moulton¹ ¹FSPM-Strukturbildugsprozesse, University of Bielefeld, Bielefeld, D-33501, Germany {dress, khuber, moulton}@mathematik.uni-bielefeld.de ²Mathematics Department, Massey University, Palmerston North, New Zealand m.hendy@massey.ac.nz Received October 20, 1997 AMS Subject Classification: 05C99, 05C05, 04A03, 03E05, 92B99 Abstract. In 1971, Peter Buneman proposed a way to construct a tree from a collection of pairwise compatible splits. This construction immediately generalizes to arbitrary collections of splits, and yields a connected median graph, called the Buneman graph. In this paper, we prove that the vertices and the edges of this graph can be described in a very simple way: given a collection of splits S, the vertices of the Buneman graph correspond precisely to the subsets S' of S such that the splits in S' are pairwise incompatible and the edges correspond to pairs (S', S) with S' as above and S ∈S'. Using this characterization, it is much more straightforward to construct the vertices of the Buneman graph than using prior constructions. We also recover as an immediate consequence of this enumeration that the Buneman graph is a tree, that is, that the number of vertices exceeds the number of edges (by one), if and only if any two distinct splits in S are compatible. Keywords: Buneman graphs, split systems, split decompositon, phylogenetic networks, phylogenetic trees, median networks, hypercubes, compatibilty of taxonomic characters References 1. H.-J. Bandelt, Phylogenetic networks, Verh. Naturwiss. Ver. Hamburg 34 (1991) 51–57. 2. H.-J. Bandelt and A. Dress, A canonical decomposition theory for metrics on a finite set, Adv. Math. 92 (1992) 47–105. 3. P. Buneman, The recovery of trees from measures of dissimilarity, In: Mathematics in the Archeological and Historical Sciences, F. Hodson et al., Eds., Edinburgh University Press, 1971, pp. 387–395. 4. J. Barthelemy, From copair hypergraphs to median graphs with latent vertices, Discrete Math. 76 (1989) 9–28. 5. J. Barthelemy and A. Guenoche, Trees and Proximity Representations, John Wiley, 1991. 6. A. Dress, D. Huson, and V. Moulton, Analyzing and visualizing distance data with the splits-tree graph, Discrete Appl. Math. 71 (1996) 95–110. 7. A. Dress, K. Huber, and V. Moulton, Some variations on a theme by Buneman, Ann. Combin. 1 (1997) 339–352. Get the LaTex \| DVI \| PS file of this abstract. back

Annals of Combinatorics 1 (1997) 329-337

On the Number of Vertices and Edges of the Buneman Graph

A. Dress¹, M. Hendy², K. Huber¹, and V. Moulton¹

¹FSPM-Strukturbildugsprozesse, University of Bielefeld, Bielefeld, D-33501, Germany
{dress, khuber, moulton}@mathematik.uni-bielefeld.de

²Mathematics Department, Massey University, Palmerston North, New Zealand
m.hendy@massey.ac.nz

Received October 20, 1997

AMS Subject Classification: 05C99, 05C05, 04A03, 03E05, 92B99

Abstract. In 1971, Peter Buneman proposed a way to construct a tree from a collection of pairwise compatible splits. This construction immediately generalizes to arbitrary collections of splits, and yields a connected median graph, called the Buneman graph. In this paper, we prove that the vertices and the edges of this graph can be described in a very simple way: given a collection of splits S, the vertices of the Buneman graph correspond precisely to the subsets S' of S such that the splits in S' are pairwise incompatible and the edges correspond to pairs (S', S) with S' as above and S ∈S'. Using this characterization, it is much more straightforward to construct the vertices of the Buneman graph than using prior constructions. We also recover as an immediate consequence of this enumeration that the Buneman graph is a tree, that is, that the number of vertices exceeds the number of edges (by one), if and only if any two distinct splits in S are compatible.

Keywords: Buneman graphs, split systems, split decompositon, phylogenetic networks, phylogenetic trees, median networks, hypercubes, compatibilty of taxonomic characters

References

1. H.-J. Bandelt, Phylogenetic networks, Verh. Naturwiss. Ver. Hamburg 34 (1991) 51–57.

2. H.-J. Bandelt and A. Dress, A canonical decomposition theory for metrics on a finite set, Adv. Math. 92 (1992) 47–105.

3. P. Buneman, The recovery of trees from measures of dissimilarity, In: Mathematics in the Archeological and Historical Sciences, F. Hodson et al., Eds., Edinburgh University Press, 1971, pp. 387–395.

4. J. Barthelemy, From copair hypergraphs to median graphs with latent vertices, Discrete Math. 76 (1989) 9–28.

5. J. Barthelemy and A. Guenoche, Trees and Proximity Representations, John Wiley, 1991.

6. A. Dress, D. Huson, and V. Moulton, Analyzing and visualizing distance data with the splits-tree graph, Discrete Appl. Math. 71 (1996) 95–110.

7. A. Dress, K. Huber, and V. Moulton, Some variations on a theme by Buneman, Ann. Combin. 1 (1997) 339–352.

Get the LaTex | DVI | PS file of this abstract.

back