On spaces extremal for the Gomory-Hu inequality

Abstract

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\in 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\to Y$ and $g:Y\to Z$ such that $X$ and $Y$ are finite ultrametric space, $X$ satisfies the above equality, $f$ is an $\epsilon$-isometry with an arbitrary $\epsilon >0$, and $g$ is a ball-preserving map.

14 pages