Metrization of Weighted Graphs

: Dovgoshey O, Martio O, Vuorinen M

Publisher: SPRINGER BASEL AG

: 2013

: Annals of Combinatorics

: ANNALS OF COMBINATORICS

: ANN COMB

: 3

: 17

: 3

: 455

: 476

: 22

: 0218-0006

DOI: https://doi.org/10.1007/s00026-013-0192-7

We find a set of necessary and sufficient conditions under which the weight on the graph G = (V, E) can be extended to a pseudometric d : V x V -> R+. We describe the structure of graphs G for which the set of all such extensions contains a metric whenever w is strictly positive. Ordering by the pointwise order, we have found that the posets contain the least elements rho (0,w) if and only if G is a complete k-partite graph with . In this case the symmetric functions f : V x V -> R+, lying between rho (0,w) and the shortest-path pseudometric, belong to for every metrizable w if and only if the cardinality of all parts in the partition of V is at most two.

Mathematics