On Spaces Extremal for the Gomory-Hu Inequality

Let (X, d) be a finite ultrametric space. In 1961 E.C. Gomory and T.C. Hu proved the inequality vertical bar Sp(X)vertical bar <= vertical bar X vertical bar where Sp(X) = {d(x, y): x, y is an element of 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 vertical bar Sp(X)vertical bar = vertical bar X vertical bar 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 e-isometry with an arbitrary epsilon > 0, and g is a ball-preserving map.