Subdominant pseudoultrametric on graphs

2011/10/31 by O. Dovgoshey, Dovgoshey, O., E. Petrov +1 · 1 citation
Mathematics · #05C10 #05C12 #54E35 #FOS: Mathematics #Metric Geometry (math.MG) #math.MG #msc:05C10 #msc:05C12 #msc:54E35

paper · pdf · doi:10.48550/arxiv.1110.6802

22 pages, 3 figures

arxiv created 2011/10/31 · arxiv updated 2011/11/01

Abstract

Let (G,w) be a weighted graph. The necessary and sufficient conditions under which a weight w : E(G)-->R⁺ can be extended to a pseudoultrametric on V(G) are found. A criterion of the uniqueness of this extension is also obtained. It is proved that G is complete k-partite with k >= 2 if and only if, for every pseudoultrametrizable weight w, there exists the smallest pseudoultrametric agreed with w. We characterize the structure of graphs for which the subdominant pseudoultrametric is an ultrametric for every strictly positive pseudoultrametrizable weight.

Cited by

• The Gomory-Hu inequality and trees

Related

• Metrization of weighted graphs
• Factorization and pseudofactorization of weighted graphs
• Weighted Regularity Lemma with Applications
• The 1-2-3 Conjecture almost holds for regular graphs
• Weighted-amenability and percolation