A1 Refereed original research article in a scientific journal
Metrization of Weighted Graphs
Authors: Dovgoshey O, Martio O, Vuorinen M
Publisher: SPRINGER BASEL AG
Publication year: 2013
Journal: Annals of Combinatorics
Journal name in source: ANNALS OF COMBINATORICS
Journal acronym: ANN COMB
Number in series: 3
Volume: 17
Issue: 3
First page : 455
Last page: 476
Number of pages: 22
ISSN: 0218-0006
DOI: https://doi.org/10.1007/s00026-013-0192-7
Abstract
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.
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.
UTU Research Portal