Compatible decompositions and block realizations of finite metrics

Abstract

Given a metric D defined oil a finite set X, we define a finite collection D of metrics on X to he a compatible decomposition of D if any two distinct metrics in D are linearly independent (considered as vectors in R-XxX), D = Sigma(d is an element of D)d holds, and there exist points x, x' is an element of X for any two distinct metrics d, d' in D such that d(x, y) d'(x', y) = 0 holds for every y is an element of X. In this paper, we show that such decompositions are ill one-to-one correspondence with (isomorphism classes of) block realizations of D, that is, graph realizations G of D for which G is a block graph and for which every vertex in G not labelled by X has degree at least 3 and is a cut point of G. This generalizes a fundamental results in phylogenetic combinations that states that a metric D defined oil X call be realized by a tree if and only if there exists a compatible decomposition D of D such that all metrics d is an element of D are split metrics, and lays the foundation for a more general theory of metric decompositions that will be explored in future papers. (c) 2007 Elsevier Ltd. All rights reserved.