Geodesic
Subdominant pseudoultrametric on graphs
Sbornik. Mathematics, Tome 204 (2013) no. 8, pp. 1131-1151 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2013},
     volume = {204},
     number = {8},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2013_204_8_a2/}
}
TY  - JOUR
AU  - A. A. Dovgoshey
AU  - E. A. Petrov
TI  - Subdominant pseudoultrametric on graphs
JO  - Sbornik. Mathematics
PY  - 2013
SP  - 1131
EP  - 1151
VL  - 204
IS  - 8
UR  - http://geodesic.mathdoc.fr/item/SM_2013_204_8_a2/
LA  - en
ID  - SM_2013_204_8_a2
ER  - 
%0 Journal Article
%A A. A. Dovgoshey
%A E. A. Petrov
%T Subdominant pseudoultrametric on graphs
%J Sbornik. Mathematics
%D 2013
%P 1131-1151
%V 204
%N 8
%U http://geodesic.mathdoc.fr/item/SM_2013_204_8_a2/
%G en
%F 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/

[1] J. A. Bondy, U. S. R. Murty, Graph Theory, Grad. Texts in Math., 244, Springer-Verlag, New York, 2008 | MR | Zbl

[2] O. Dovgoshey, O. Martio, M. Vuorinen, Metrization of weighted graphs, Reports in Math. University of Helsinki, 516, 2011

[3] O. Dovgoshey, O. Martio, “Blow up of balls and coverings in metric spaces”, Manuscripta Math., 127:1 (2008), 89–120 | DOI | MR | Zbl

[4] N. Jardine, R. Sibson, Mathematical taxonomy. Part II, Willey, London, 1971 | MR | Zbl

[5] J. M. Bayod, J. Martiner-Maurica, “Subdominant ultrametrics”, Proc. Amer. Math. Soc., 109:3 (1990), 829–834 | DOI | MR | Zbl

[6] J. P. J. Jardine, N. Jardine, R. Sibson, “The structure and construction of taxonomic hierarchies”, Math. Bioscienes, 1:2 (1967), 173–179 | DOI | Zbl

[7] R. Rammal, J. C. Angles d'Auriac, B. Doucot, “On the degree of ultrametricity”, J. Physique, 46 (1985), 945–952 | DOI | MR

[8] R. Rammal, G. Toulouse, M. A. Virasoro, “Ultrametricity for physicist”, Rev. Modern Phys., 58:3 (1986), 765–788 | DOI | MR

[9] D. Marcu, “A study on metrics and statistical analysis”, Studia Univ. Babes-Bolyai Math., 49:3 (2004), 43–74 | MR | Zbl

[10] O. Dovgoshey, D. Dordovskyi, “Ultrametricity and metric betweenness in tangent spaces to metric spaces”, p-Adic Numbers Ultrametric Anal. Appl., 2:2 (2010), 100–113 | DOI | MR | Zbl

[11] A. J. Lemin, “On ultrametrization of general metric spaces”, Proc. Amer. Math. Soc., 131:3 (2003), 979–989 | DOI | MR | Zbl

[12] D. Dordovskyi, O. Dovgoshey, E. Petrov, “Diameter and diametrical pairs of points in ultrametric spaces”, p-Adic Numbers Ultrametric Anal. Appl., 3:4 (2011), 253–262 | DOI | MR | Zbl

[13] S. B. Nadler, jr., Continuum theory. An introduction, Monogr. Textbooks Pure Appl. Math., 158, Marcel Dekker, New York, 1992 | MR | Zbl

[14] A. G. O'Farrel, “When uniformly-continuous implies bounded”, Irish Math. Soc. Bull., 53 (2004), 53–56 | MR | Zbl