The Gomory-Hu inequality and trees

2026/04/20 by Oleksiy Dovgoshey, Olga Rovenska · 1 voice
Mathematics · #math.GN

paper · pdf

Abstract

Let G=(V,E) be a finite connected graph with vertex set V and edge set E, and let U(G) be the set of all ultrametric spaces (V,d_l) generated by vertex labelings l\colon V → \mathbb R⁺. We prove that the inequality |D(V)| ≤ |E| + 1 holds for all (V,d_l) ∈ U(G), where D(V) is the distance set of (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.

Citations

• Center of distances of ultrametric spaces generated by labeled trees
• Forbidden Four Cycle, Star Graphs and Isometric Embeddings
• Labeled Trees Generating Separable and Locally Finite Ultrametrics
• Compact ultrametric spaces generated by labeled star graphs
• Ultrametric spaces generated by labeled star graphs
• Totally bounded ultrametric spaces generated by labeled rays
• Locally finite ultrametric spaces and labeled trees
• Labeled trees generating complete, compact, and discrete ultrametric spaces
• Isomorphism of trees and isometry of ultrametric spaces
• How rigid the finite ultrametric spaces can be?
• On spaces extremal for the Gomory-Hu inequality
• Subdominant pseudoultrametric on graphs
• Metrization of weighted graphs
• Ultrametricity for physicists

Discussions

• Oleksiy Dovgoshey, Olga Rovenska: The Gomory-Hu inequality and trees https://arxiv.org/abs/2604.18400 https://arxiv.org/pdf/2604.18400 https://arxiv.org/html/2604.18400 [bsky, 0 points, 0 comments]

Related

• On the Gomori-Hu inequality
• On spaces extremal for the Gomory-Hu inequality
• Labeled Trees Generating Separable and Locally Finite Ultrametrics
• Longest paths in trees and isometricity of ultrametric spaces
• Labeled trees generating complete, compact, and discrete ultrametric spaces