The Gomory-Hu inequality and trees
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 \to \mathbb R^+$. We prove that the inequality $$ |D(V)| \le |E| + 1 $$ holds for all $(V,d_l) \in 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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.18400
curl -X POST /api/v1/records/arxiv/2604.18400/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.18400/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'