On spaces extremal for the Gomory-Hu inequality

DOI10.1134/S2070046615020053MaRDI QIDQ498716zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 3080144 (Why is no real title available?)
• Automata, dynamical systems, and groups
• Characterizing (quasi-)ultrametric finite spaces in terms of (directed) graphs
• Exact enumeration of cherries and pitchforks in ranked trees under the coalescent model
• Graph theory
• Mappings preserving balls of finite ultrametric spaces
• Multi-Terminal Network Flows
• On the Gomory-Hu inequality
• Subdominant pseudoultrametric on graphs
• Trees and ultrametric spaces: A categorical equivalence
• Weak similarities of metric and semimetric spaces

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
• Ultrametric preserving functions and weak similarities of ultrametric spaces
• On ultrametric-preserving functions
• 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

Describes a project that uses

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)