Concerning the relationship between realizations and tight spans of finite metrics

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.