Higgins, J.; Campbell, D. Prescribed ultrametrics. (English) Zbl 0786.54031 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 PDF BibTeX XML Cite \textit{J. Higgins} and \textit{D. Campbell}, RAIRO, Inform. Théor. Appl. 27, No. 1, 1--5 (1993; Zbl 0786.54031) Full Text: DOI EuDML OpenURL 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 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.