Abstract:
Let $(G,w)$ be a weighted graph. We find necessary and sufficient conditions under which the weight $w\colon E(G)\to \mathbb{R}^+$ can be extended to a pseudoultrametric on $V(G)$, and establish a criterion for the uniqueness of such an extension. We demonstrate that $(G,w)$ is a complete $k$-partite graph, for $k\geqslant 2$, if and only if for any weight that can be extended to a pseudoultrametric, among all such extensions one can find the least pseudoultrametric consistent with $w$. We give a structural characterization of graphs for which the subdominant pseudoultrametric is an ultrametric for any strictly positive weight that can be extended to a pseudoultrametric.
Bibliography: 14 titles.
Fulltext:
PDF file (611 kB)
