Ultrametrics and Complete Multipartite Graphs

Abstract

Let \((X, d)\) be a semimetric space and let \(G\) be a graph. We say that \(G\) is the diametrical graph of \((X, d)\) if \(X\) is the vertex set of \(G\) and the adjacency of vertices \(x\) and \(y\) is equivalent to the equality \(\diam X = d(x, y)\). It is shown that a semimetric space \((X, d)\) with diameter \(d^*\) is ultrametric iff the diametrical graph of \((X, d_{\varepsilon})\) with \(d_{\varepsilon}(x, y) = \min\{d(x, y), \varepsilon\}\) is complete multipartite for every \(\varepsilon \in (0, d^*)\). A refinement of the last result is given for totally bounded ultrametric 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.

Keywords

• totally bounded ultrametric space
• compact ultrametric space
• complete multipartite graph
• weak similarity