  Let $G$ be a simple graph. Consider all weightings of the vertices of $G$
with real numbers whose total sum is nonnegative. How many edges of $G$ have
endpoints with a nonnegative sum? We consider the minimum number of such edges
over all such weightings as a graph parameter. Computing this parameter has
been shown to be NP-hard but we give a polynomial algorithm to compute the
minimum of this parameter over realizations of a given degree sequence. We also
completely determine the minimum and maximum value of this parameter for
regular graphs.

Combinatorics