Premium
Gomory‐Hu trees of infinite graphs with finite total weight
Author(s) -
Joó Attila
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22207
Subject(s) - mathematics , combinatorics , tree (set theory) , graph , discrete mathematics , finite set , mathematical analysis
A well‐known theorem of Gomory and Hu states that if G is a finite graph with nonnegative weights on its edges, then there exists a tree T (now called a Gomory‐Hu tree) on V ( G ) such that for all u ≠ v ∈ V ( G ) there is an e ∈ E ( T ) such that the two components of T − e determine an optimal (minimal valued) cut between u an v in G . In this article, we extend their result to infinite weighted graphs with finite total weight. Furthermore, we show by an example that one cannot omit the condition of the finiteness of the total weight.