Optimal realizations of generic five-point metrics
SCIE
SCOPUS
- Title
- Optimal realizations of generic five-point metrics
- Authors
- Koolen, J; Lesser, A; Moulton, V
- Date Issued
- 2009-07
- Publisher
- ACADEMIC PRESS LTD ELSEVIER SCIENCE L
- Abstract
- Given a metric cl oil a finite set X, a realization of d is a triple (G, phi, omega) consisting of a graph G = (V, E), a labeling phi : X -> V, and a weighting omega : E -> R(>0) such that for all x, y is an element of X the length of any shortest path in G between phi(x) and phi(y) equals d(x, y). Such a realization is called optimal if parallel to G parallel to := Sigma(e is an element of E) omega(e) is minimal amongst all realizations of d. In this paper we will consider optimal realizations of generic five-point metric spaces. In particular, we show that there is a canonical subdivision C Of the metric fail of five-point metrics into cones such that (i) every metric d in the interior of a cone C is an element of C has a unique optimal realization (G, phi, omega), (ii) if d' is also in the interior of C with optimal realization (G', phi', omega') then (G, phi) and (G', phi') are isomorphic as labeled graphs, and (iii) any labeled graph that underlies all optimal realizations of the metrics in the interior of some cone C e C must belong to one of three isomorphism classes. (C) 2008 Elsevier Ltd. All rights reserved.
- Keywords
- GRAPHS
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/27573
- DOI
- 10.1016/j.ejc.2008.09.021
- ISSN
- 0195-6698
- Article Type
- Article
- Citation
- EUROPEAN JOURNAL OF COMBINATORICS, vol. 30, no. 5, page. 1164 - 1171, 2009-07
- 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.