On the Gomory-Hu inequality

DOI10.1007/S10958-014-1798-YzbMATH Open1348.54020arXiv1211.2389OpenAlexW2020744938MaRDI QIDQ460733FDOQ460733

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)

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.

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

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

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)

Cites Work

• A course in metric geometry
• Title not available (Why is that?)
• Trees and ultrametric spaces: A categorical equivalence
• The number of trees
• Automata, dynamical systems, and groups
• Multi-Terminal Network Flows
• 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

Cited In (19)

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

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)