Gomory-Hu trees of countably infinite graphs with finite total weight

Abstract

Gomory and Hu proved in [1] their well-known theorem which states that if $G$ is a finite graph with non-negative weights on its edges, then there exists a tree $T$ (called now Gomory-Hu tree) on $V(G)$ such that for all $u \neq v \in V(G)$ there is an $e \in E(T)$ such that the two components of $T-e$ determine an optimal (minimal valued) cut between $u$ an $v$ in $G$. In this paper we extend their result to countably infinite weighted graphs with finite total weight. Furthermore, we show by an example that one can not omit the condition of finiteness of the total weight.

Bibtex entry:

@techreport{egres-16-02,
AUTHOR = {Jo{\'o}, Attila},
TITLE = {Gomory-Hu trees of countably infinite graphs with finite total weight},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2016},
NUMBER = {TR-2016-02}
}