On optimal realizations of finite metric spaces by graphs (Q1100481): Difference between revisions

Let \(G=G(V,E,w)\) be a finite undirected simple graph with vertex set V, edge set E, and \(w: E\to {\mathbb{R}}^+\) a function that assigns a positive weight (or length) to every edge of G. let \(d_ G(x,y)\) denote the length of a shortest path from vertex x to vertex y in G. The weighted graph G realizes a finite metric (M,d) if \(M\subset V\) and \(d(i,j)=d_ G(i,j)\) for all i, j of M. A realization G(V,E,w) of (M,d) is optimal if \(\sum_{e\in E}w(e)\) is minimal among all realizations of (M,d). The author presents several new results on this topic. In particular, he gives an example of a metric with a continuum of optimal realizations, thus disproving a conjecture of \textit{A. W. M. Dress} [Adv. Math. 53, 321- 402 (1984; Zbl 0562.54041)].