Subdominant pseudoultrametric on graphs
Sbornik. Mathematics, Tome 204 (2013) no. 8, pp. 1131-1151
Voir la notice de l'article provenant de la source Math-Net.Ru
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.
Keywords:
weighted graph, infinite graph, ultrametric space, shortest path metric, complete $k$-partite graph.
@article{SM_2013_204_8_a2,
author = {A. A. Dovgoshey and E. A. Petrov},
title = {Subdominant pseudoultrametric on graphs},
journal = {Sbornik. Mathematics},
pages = {1131--1151},
publisher = {mathdoc},
volume = {204},
number = {8},
year = {2013},
language = {en},
url = {http://geodesic.mathdoc.fr/item/SM_2013_204_8_a2/}
}
A. A. Dovgoshey; E. A. Petrov. Subdominant pseudoultrametric on graphs. Sbornik. Mathematics, Tome 204 (2013) no. 8, pp. 1131-1151. http://geodesic.mathdoc.fr/item/SM_2013_204_8_a2/