On the Gomory-Hu inequality

DOI10.1007/S10958-014-1798-YMaRDI QIDQ460733zbMATHOpenAlexFDO

Authors E. A. Petrov, Aleksey A. Dovgoshey

Publication date 14 October 2014

Published in Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

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

zbMATH Keywords

complete bipartite graphball-preserving mappingfinite ultrametric spaceGromov-Hausdorff metricspectrum of an ultrametric spacestrictly binary tree

Mathematics Subject Classification ID

Metric spaces, metrizability (54E35)

Abstract: It was proved by Gomori and Hu in 1961 that for every finite nonempty ultrametric space $(X,d)$ the following inequality $|Sp(X)|leqslant|X|-1$ holds with $Sp(X)=d(x,y):x,yinX,xeqy$. We characterize the spaces $X$, for which the equality in this inequality is attained by the structural properties of some graphs and show that the set of isometric types of such $X$ is dense in the Gromov-Hausdorff space of the compact ultrametric spaces.

Recommendations

• On spaces extremal for the Gomory-Hu inequality
• On an inequality of G. Szegö
• On an inequality of G. H. Hardy
• On Gasparyan's inequality
• Publication:3485655
• On an inequality of Bogar and Gustafson
• On G. Bennett's inequality
• scientific article; zbMATH DE number 3901079
• On Gardner-Hartenstine's inequality
• scientific article; zbMATH DE number 1995864

Cites work

• scientific article; zbMATH DE number 2018401 (Why is no real title available?)
• A course in metric geometry
• Automata, dynamical systems, and groups
• Characterizing (quasi-)ultrametric finite spaces in terms of (directed) graphs
• Diameter and diametrical pairs of points in ultrametric spaces
• Mappings preserving balls of finite ultrametric spaces
• Multi-Terminal Network Flows
• The number of trees
• Trees and ultrametric spaces: A categorical equivalence

Cited in

(19)

• From isomorphic rooted trees to isometric ultrametric spaces
• Locally Finite ultrametric spaces and labeled trees
• On some extremal properties of finite ultrametric spaces
• Hereditary properties of finite ultrametric spaces
• On quasisymmetric mappings between ultrametric spaces
• On ultrametric-preserving functions
• Properties and morphisms of finite ultrametric spaces and their representing trees
• Combinatorial properties of ultrametrics and generalized ultrametrics
• Weak similarities of finite ultrametric and semimetric spaces
• The comb representation of compact ultrametric spaces
• On spaces extremal for the Gomory-Hu inequality
• Ultrametric preserving functions and weak similarities of ultrametric spaces
• Finite ultrametric balls
• Minimum spanning paths and Hausdorff distance in finite ultrametric spaces
• The Bhargava greedoid as a Gaussian elimination greedoid
• Uniqueness of best proximity pairs and rigidity of semimetric spaces
• Labeled trees generating complete, compact, and discrete ultrametric spaces
• Bipartite graphs and best proximity pairs
• How rigid the finite ultrametric spaces can be?

This page was built for publication: On the Gomory-Hu inequality

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