Concerning the relationship between realizations and tight spans of finite metrics
SCIE
SCOPUS
- Title
- Concerning the relationship between realizations and tight spans of finite metrics
- Authors
- Koolen, J; Lesser, A; Moulton, V
- Date Issued
- 2007-10
- Publisher
- SPRINGER
- Abstract
- Given a metric d on a finite set X, a realization of d is a weighted graph G = (V, E, w: E -> R->0) with X subset of V such that for all x, y is an element of X the length of any shortest path in G between x and y equals d(x, y). In this paper we consider two special kinds of realizations, optimal realizations and hereditarily optimal realizations, and their relationship with the so-called tight span. In particular, we present an infinite family of metrics {d(k)}(k >= 1), and-using a new characterization for when the so-called underlying graph of a metric is an optimal realization that we also present-we prove that d(k) has (as a function of k) exponentially many optimal realizations with distinct degree sequences. We then show that this family of metrics provides counter-examples to a conjecture made by Dress in 1984 concerning the relationship between optimal realizations and the tight span, and a negative reply to a question posed by Althofer in 1988 on the relationship between optimal and hereditarily optimal realizations.
- Keywords
- SPACES; GRAPHS
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/29505
- DOI
- 10.1007/S00454-007-1
- ISSN
- 0179-5376
- Article Type
- Article
- Citation
- DISCRETE & COMPUTATIONAL GEOMETRY, vol. 38, no. 3, page. 605 - 614, 2007-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.