Compatible decompositions and block realizations of finite metrics
SCIE
SCOPUS
- Title
- Compatible decompositions and block realizations of finite metrics
- Authors
- Dress, AWM; Huber, KT; Koolen, J; Moulton, V
- Date Issued
- 2008-10
- Publisher
- ACADEMIC PRESS LTD ELSEVIER SCIENCE L
- 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.
- Keywords
- GRAPHS; SPACES; TREES
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/29343
- DOI
- 10.1016/J.EJC.2007.1
- ISSN
- 0195-6698
- Article Type
- Article
- Citation
- EUROPEAN JOURNAL OF COMBINATORICS, vol. 29, no. 7, page. 1617 - 1633, 2008-10
- 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.