2011/05/31 by Oleksiy Dovgoshey, Олли Мартио, Dovgoshey, Oleksiy +5 · 1 citation
Computer Science · Mathematics · #05C10 #05C12 #54E35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO #msc:05C10 #msc:05C12 #msc:54E35
paper · pdf · doi:10.48550/arxiv.1105.6167
7 figures
arxiv created 2011/05/31 · openalex publication_date 2011/05/31 · arxiv updated 2011/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We find a set of necessary and sufficient conditions under which the weight w:E→\mathbb R+ on the graph G=(V,E) can be extended to a pseudometric d:V× V→\mathbb R+. If these conditions hold and G is a connected graph, then the set \mathfrak Mw of all such extensions is nonvoid and the shortest-path pseudometric dw is the greatest element of \mathfrak Mw with respect to the partial ordering d1 \leqslant d2 if and only if d1(u,v) \leqslant d2(u,v) for all u,v∈ V. It is shown that every nonvoid poset (\mathfrak Mw,\leqslant) contains the least element ρ0,w if and only if G is a complete k-partite graph with k\geqslant 2 and in this case the explicit formula for computation of ρ0,w is obtained.