The Gomory-Hu inequality and trees

Oleksiy Dovgoshey, Olga Rovenska · 2026

Read The Gomory-Hu inequality and trees by Oleksiy Dovgoshey, Olga Rovenska (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-18400.txt.

Introduction

Dovgoshey and Rovenska prove a Gomory-Hu-type inequality for ultrametric spaces generated by vertex labels. For a finite connected graph, the count of distinct distance values is at most the number of edges plus one. The authors find exactly when a tie holds. They also show every graph of that kind with labels that never drop below zero yields a pseudoultrametric space, with conditions for it to be a true member of that family.

Catalog record

CREATOROleksiy Dovgoshey, Olga Rovenska
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32590
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.18400

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Gomory-Hu inequality and trees Oleksiy Dovgoshey, Olga Rovenska Abstract Let G = ( V , E ) G=(V,E) be a finite connected graph with vertex set V V and edge set E E , and let U ⁡ ( G ) U(G) be the set of all ultrametric spaces ( V , d l ) (V,d_{l}) generated by vertex labelings l : V → ℝ + l\colon V\to\mathbb{R}^{+} . We prove that the inequality | D ⁡ ( V ) | ≤ | E | + 1 |D(V)|\leq|E|+1 holds for all ( V , d l ) ∈ U ⁡ ( G ) (V,d_{l})\in U(G) , where D ⁡ ( V ) D(V) is the distance set of ( V , d l ) (V,d_{l}) . The necessary and sufficient conditions under which the above inequality turns to an equality are found. Moreover, we prove that each connected graph with non-negative vertex labeling generates a pseudoultrametric space and find some sufficient conditions under which this space is ultrametric. MSC Classification]Primary 54E35. Secondary 05C05. keywords distance set, pseudoultrametric space, tree, ultrametric space, vertex labeling. pacs [ 1 Introduction The theory of ultrametric spaces is closely connected with problems of applied mathematics, physics, linguistics, psychology, and computer science, see, for example, Rammal et al. 1986 ; Murtagh et al. 2008 ; Lemin 2003 ; Murtagh 2004 ; Krötzsch 2006 ; Seda and Hitzler 2008 ; Priess-Crampe and Ribenboim 2000 . By studying the flows in networks, R. Gomory and T. Hu Gomory and Hu 1961 deduced a statement that can be formulated as follows: If (X,d) is a finite ultrametric space with distance set D(X):=\{d(x,y):x,y\in X\}, then the inequality |D(X)|\leq|X| (1) holds. We will call inequality ( 1 ) the Gomory–Hu inequality . Definition 1.1 . A finite ultrametric space (X,d) is said to be a {\bf GH} -space if the equality |D(X)|=|X| holds. In what follows we denote by {\bf GH} the class of all {\bf GH} -spaces. Two descriptions of the class {\bf GH} were obtained in terms of the representing trees of finite ultrametric spaces and, respectively, so-called diametrical graphs of such spaces (see Petrov and Dovgoshey 2014 , Theorem 2.3 and Theorem 3.1). A criterion of (X,d)\in{\bf GH} in terms of weighted Hamiltonian cycles and weighted Hamiltonian paths are found in Theorem 2.5 of paper Dovgoshey et al. 2015 . The number of non-isometric spaces (X,d)\in{\bf GH} are also calculated in Dovgoshey et al. 2015 . The finite ultrametric spaces (X,d) with |X|\geq 3 for which every self-isometry X\to X has at least |X|-2 fixed points give us an interesting example of {\bf GH} -spaces. (See Theorem 2.3 of Petrov and Dovgoshey 2014 and Theorem 3.4 of Dovgoshey et al. 2017 .) At the present paper we investigate the ultrametric spaces generated by connected graphs G with given vertex labelings l:V(G)\to\mathbb{R}^{+} . The ultrametric spaces generated by labeled trees were introduced in Dovgoshey 2020 . Some results describing the metric and topological properties of such spaces can be found in Dovgoshey et al. 2025 ; Dovgoshey and Kostikov 2023 ; Dovgoshey and Küçükaslan 2022 ; Dovgoshey and Rovenska 2026a ; Dovgoshey and Rovenska 2026b ; Dovgoshey and Rovenska 2026c ; Dovgoshey and Rovenska 2025 ; Dovgoshey and Vito 2025 . The present paper is organized as follows. In Section 2 we collect together some definitions and facts related to ultrametric spaces and graphs. The main results of the paper are presented in Section 3 . Theorem 3.3 , the first theorem of Section 3 , shows that every connected labeled graph G generates a pseudoultrametric on V(G) . Moreover, we show that this pseudoultrametric is an ultrametric if G is locally finite. The necessary and sufficient conditions under which an ultrametric space generated by finite labeled tree belongs to the class \bf GH are given in Theorem 3.8 . Theorem 3.10 contains a partial generalization of Theorem 3.8 to the case of ultrametric spaces generated by arbitrary finite connected labeled graphs. In Proposition 3.12 we prove that every finite connected labeled graph G(l) generates a \bf GH -space for some suitable vertex labeling l . Example 3.13 describes the vertex labelings on complete finite graphs which generate \bf GH -spaces. The final Section 4 contains new conjectures and some open problems. 2 Preliminaries Recall some necessary definitions from the theory of metric spaces and the graph theory. Let X be a non-empty set. An ultrametric on X is a function d:X\times X\to\mathbb{R}^{+} , \mathbb{R}^{+}:=[0,\infty) , such that for all x,y,z\in X : (i) d(x,y)=d(y,x) , (ii) d(x,y)=0\iff x=y , (iii) d(x,y)\leq\max\{d(x,z),d(z,y)\} . Inequality (iii) is often called the strong triangle inequality . If we replace condition (ii) by the weaker condition d(x,x)=0, then d is called a pseudoultrametric on X . Just as in the case of an ultrametric space, we introduce the distance set D(X) of a pseudoultrametric space (X,d) as D(X):=\{d(x,y):x,y\in X\}. The following proposition directly follows from Theorem 14 in Chapter 4 of book Kelley 1975 . Proposition 2.1 . Let (X,d) be a pseudoultrametric space. Then there exists Y\subseteq X such that the function \rho:=d|_{Y\times Y} is an ultrametric on Y and the equality D(X)=D(Y) holds, where D(X) and, respectively, D(Y) are the distance sets of the pseudoultrametric space (X,d) and the ultrametric space (Y,\rho) . Let us turn now to the graph theory. Recall that a graph is a pair (V,E) consisting of a non-empty set V and a (possibly empty) set E whose elements are unordered pairs of distinct points from V . For a graph G=(V,E) , the sets V=V(G) and E=E(G) are called the set of vertices and the set of edges , respectively. If x and y are vertices of G and \{x,y\}\in E(G) , then we say that x and y are adjacent in G . A graph G is said to be empty if the equality E(G)=\emptyset holds. A graph H is called a subgraph of a graph G , H\subseteq G , if the inclusions V(H)\subseteq V(G)\quad\text{and}\quad E(H)\subseteq E(G) hold. A graph G is said to be finite if this graph contains a finite number of vertices, |V(G)|<\infty . Let v be a vertex of a graph G . The cardinal number of the set \{u\in V(G):\{u,v\}\in E(G)\} is the degree of v . The degree of v\in V(G) will be denoted by \delta_{G}(v) , \delta_{G}(v):=\left|\{u\in V(G):\{u,v\}\in E(G)\}\right|. (2) A graph G is called locally finite if the degree \delta_{G}(v) is finite, \delta_{G}(v)<\infty, for every v\in V(G) . The next theorem is a special case of Theorem 1.2 of book Bondy and Murty 2008 . Theorem 2.2 . Let G be a finite graph. Then the equality 2|E(G)|=\sum_{v\in V(G)}\delta_{G}(v) holds. A path is a graph P=(V,E) of the form V=\{x_{0},x_{1},\dots,x_{k}\},\quad E=\{\{x_{0},x_{1}\},\dots,\{x_{k-1},x_{k}\}\}, (3) where all x_{i} are distinct and k\geq 1 . If ( 3 ) holds, then we write P=(x_{0},\ldots,x_{k}) and say that P is a path joining the vertices x_{0} and x_{k} . A graph G is called connected if for any two distinct vertices u,v\in V(G) there exists a path P\subseteq G joining these vertices. In particular, any graph G with |V(G)|=1 is connected. A finite graph C is a cycle if |V(C)|\geq

Read the complete text