Prescribed ultrametrics. (English) Zbl 0786.54031

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.


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
Full Text: DOI EuDML


[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.