On spaces extremal for the Gomory-Hu inequality

DOI10.1134/S2070046615020053zbMATH Open1343.05072arXiv1412.1979OpenAlexW1662909231MaRDI QIDQ498716FDOQ498716

Authors: Aleksey A. Dovgoshey, E. A. Petrov, Hanns-Martin Teichert 

Publication date: 29 September 2015

Published in: \(p\)-Adic Numbers, Ultrametric Analysis, and Applications (Search for Journal in Brave)

Abstract: Let $(X,d)$ be a finite ultrametric space. In 1961 E.C. Gomory and T.C. Hu proved the inequality $|Sp(X)|leqslant|X|$ where $Sp(X)=d(x,y)colonx,yinX$. Using weighted Hamiltonian cycles and weighted Hamiltonian paths we give new necessary and sufficient conditions under which the Gomory-Hu inequality becomes an equality. We find the number of non-isometric $(X,d)$ satisfying the equality $|Sp(X)|=|X|$ for given $Sp(X)$. Moreover it is shown that every finite semimetric space $Z$ is an image under a composition of mappings $fcolonXoY$ and $gcolonYoZ$ such that $X$ and $Y$ are finite ultrametric space, $X$ satisfies the above equality, $f$ is an $varepsilon$-isometry with an arbitrary $varepsilon>0$, and $g$ is a ball-preserving map.

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

Recommendations

• On the Gomory-Hu inequality
• Embeddings of Ultrametric Spaces in Finite Dimensional Structures
• Metric and ultrametric spaces of resistances
• Sur les inégalités valides dans \(L^ 1\)
• Gomory‐Hu trees of infinite graphs with finite total weight

zbMATH Keywords

weighted graphbinary treefinite ultrametric space\(\epsilon\)-isometryballpreserving mappingweak similarity

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Eulerian and Hamiltonian graphs (05C45) Signed and weighted graphs (05C22) Enumeration in graph theory (05C30) Paths and cycles (05C38) Topological spaces with richer structures (54E99) Semimetric spaces (54E25)

Cites Work

• Title not available (Why is that?)
• Graph theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Trees and ultrametric spaces: A categorical equivalence
• Automata, dynamical systems, and groups
• Multi-Terminal Network Flows
• Exact enumeration of cherries and pitchforks in ranked trees under the coalescent model
• Characterizing (quasi-)ultrametric finite spaces in terms of (directed) graphs
• On the Gomory-Hu inequality
• Mappings preserving balls of finite ultrametric spaces
• Weak similarities of metric and semimetric spaces
• Subdominant pseudoultrametric on graphs

Cited In (15)

• Labeled trees generating complete, compact, and discrete ultrametric spaces
• Combinatorial properties of ultrametrics and generalized ultrametrics
• The range of ultrametrics, compactness, and separability
• How rigid the finite ultrametric spaces can be?
• On some extremal properties of finite ultrametric spaces
• On 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
• 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

Uses Software

• OEIS

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

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