Ultrametrics and complete multipartite graphs

Abstract

We describe the class of graphs for which all metric spaces with diametrical graphs belonging to this class are ultrametric. It is shown that a metric space $(X,d)$ is ultrametric iff the diametrical graph of the metric $d_{\epsilon }(x,y)=\max \{d(x,y),\epsilon \}$ is either empty or complete multipartite for every $\epsilon >0$. A refinement of the last result is obtained for totally bounded spaces. Moreover, using complete multipartite graphs we characterize the compact ultrametrizable topological spaces. The bounded ultrametric spaces, which are weakly similar to unbounded ones, are also characterized via complete multipartite graphs.

14 pages