Portal de Periódicos da CAPES

On spaces extremal for the Gomory-Hu inequality

2015; Pleiades Publishing; Volume: 7; Issue: 2 Linguagem: Inglês

10.1134/s2070046615020053

2070-0474

Oleksiy Dovgoshey, Evgeniy Petrov, Hanns‐Martin Teichert,

Algebraic Geometry and Number Theory

Let (X, d) be a finite ultrametric space. In 1961 E.C. Gomory and T.C. Hu proved the inequality |Sp(X)| ⩽ |X| where Sp(X) = {d(x, y): x, y ∈ X}. 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 f: X → Y and g: Y → Z such that X and Y are finite ultrametric spaces, X satisfies the above equality, f is an ɛ-isometry with an arbitrary ɛ > 0, and g is a ball-preserving map.