Prescribed ultrametrics. (English) Zbl 0786.54031

Higgins, J.; Campbell, D.

RAIRO, Inform. Théor. Appl. 27, No. 1, 1-5 (1993).

Summary: Let \(G=(S,E)\) be a subgraph of \(K_ n= (S,F)\), the complete graph on \(n\) vertices. Let \(\nu\) be a function from \(E\) to \(R^ +\). We prove two theorems on the extensibility of \(\nu\). Every function \(\nu\) extends to a metric on \(F\) iff \(G\) is a forest. The function \(\nu\) extends to an ultrametric on \(F\) if and only if for all non-trivial cycles \(p\) in \(G\), \(\text{mult}(p)>1\), where \(\text{mult}(p)\) depends on the values of \(\nu\) on paths.

MSC:

54E35	Metric spaces, metrizability
68R10	Graph theory (including graph drawing) in computer science
05C05	Trees
68Q25	Analysis of algorithms and problem complexity
54C20	Extension of maps

Keywords:

metric; forest; ultrametric

References:

[1]	1. M. ASCHBACHER P. BALDI, E. BAUM and R. WILSON, Embeddings of ultrametric Spaces in Finite Dimensional Structures, S.I.A.M. J. Algebra Disc. Math., 1987, 8, pp. 564-587. Zbl0639.51018 MR918059 · Zbl 0639.51018
[2]	2. V. Z. FEINBERG, Finite Ultrametric Spaces, Dokl. Akad. Nauk S.S.S.R., 1972, 202, pp. 775-778. Zbl0243.54026 MR294184 · Zbl 0243.54026
[3]	3. M. KRV’ANEK, The Complexity of Ultrametric Partitions on Graphs, Inform. Process. Lett., 1988, pp. 265-270. Zbl0637.68047 MR942581 · Zbl 0637.68047
[4]	4. N. PARGA and M. VIRASORO, The Ultrametric Organization of Memories in A Neural Network, J. Physique, 1986, 47, pp. 1857-1864. MR869145
[5]	5. A. C. M. VAN ROUIJ, Non Archimedean Functional Analysis, Marcel Dekker, New York, 1978. Zbl0396.46061 MR512894 · Zbl 0396.46061