Subdominant pseudoultrametric on graphs

DOI10.1070/SM2013V204N08ABEH004333MaRDI QIDQ2863127zbMATH OpenOpenAlexFDO

Authors E. A. Petrov, Aleksey A. Dovgoshey

Publication date 21 November 2013

Published in Sbornik: Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.6802

zbMATH Keywords

complete \(k\)-partite graphinfinite graphshortest path metricultrametric spaceweighted graph

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Metric spaces, metrizability (54E35)

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.

Recommendations

• Ultrametrization of weighted graphs
• Metrization of weighted graphs
• Prescribed ultrametrics
• Isomorphism of trees and isometry of ultrametric spaces
• The complexity of ultrametric partitions on graphs

Cites work

• Blow up of balls and coverings in metric spaces
• Diameter and diametrical pairs of points in ultrametric spaces
• Graph theory
• scientific article; zbMATH DE number 53928 (Why is no real title available?)
• scientific article; zbMATH DE number 3504320 (Why is no real title available?)
• scientific article; zbMATH DE number 2170784 (Why is no real title available?)
• scientific article; zbMATH DE number 2201862 (Why is no real title available?)
• Metrization of weighted graphs
• On ultrametrization of general metric spaces
• Subdominant Ultrametrics
• The structure and construction of taxonomic hierarchies
• Ultrametricity and metric betweenness in tangent spaces to metric spaces

Cited in

(24)

• Combinatorial properties of ultrametrics and generalized ultrametrics
• The range of ultrametrics, compactness, and separability
• Ultrametric preserving functions and weak similarities of ultrametric spaces
• Finite ultrametric balls
• On some extremal properties of finite ultrametric spaces
• Properties and morphisms of finite ultrametric spaces and their representing trees
• How rigid the finite ultrametric spaces can be?
• Extending proper metrics
• Uniqueness of best proximity pairs and rigidity of semimetric spaces
• Bipartite graphs and best proximity pairs
• Subdominant Ultrametrics
• Metrization of weighted graphs
• Ultrametrization of weighted graphs
• On spaces extremal for the Gomory-Hu inequality
• On the uniqueness of continuation of a partially defined metric
• On ultrametric-preserving functions
• Prescribed ultrametrics
• On dense subsets in spaces of metrics
• A factorization of metric spaces
• Simultaneous extensions of metrics and ultrametrics of high power
• Delhomme-Laflamme-Pouzet-Sauer space as groupoid
• Compact ultrametric spaces generated by labeled star graphs
• Totally bounded ultrametric spaces generated by labeled rays
• An embedding, an extension, and an interpolation of ultrametrics

This page was built for publication: Subdominant pseudoultrametric on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2863127)