Bipartite subgraphs of integer weighted graphs Original Research Article

For every integer p > 0, let f(p) be the minimum possible value of the maximum weight of a cut in an integer weighted graph with total weight p. It is shown that for every large n and every m < n, f((2n) + m) = ⌊14n2⌋ + min(⌈12n⌉, f(m)). This supplies the precise value of f(p) for many values of p including, e.g., all p = (2n) + (2m) when n is large enough and 14m2 ⩽ 12n.