On maximum weight of a bipartite graph of given order and size
Mirko Horňák, Stanislav Jendrol′, Ingo Schiermeyer · Discussiones Mathematicae Graph Theory · 2013
The weight of an edge xy of a graph is defined to be the sum of degrees of the vertices x and y.The weight of a graph G is the minimum of weights of edges of G.More than twenty years ago Erdős was interested in finding the maximum weight of a graph with n vertices and m edges.This paper presents a complete solution of a modification of the above problem in which a graph is required to be bipartite.It is shown that there is a function w * (n, m) such that the optimum weight is either w * (n, m) or w * (n, m) + 1.