On the minimal sum of edges in a signed edge-dominated graph (Q2170791)

Summary: Let \(G\) be a simple graph with \(n\) vertices and \(\pm 1\)-weights on edges. Suppose that for every edge \(e\) the sum of edges adjacent to \(e\) (including \(e\) itself) is positive. Then the sum of weights over edges of \(G\) is at least \(-\frac{n^2}{25} \). Also we provide an example of a weighted graph with described properties and the sum of weights \(-(1+o(1))\frac{n^2}{8(1 + \sqrt{2})^2}\). The previous best known bounds were \(-\frac{n^2}{16}\) and \(-(1+o(1))\frac{n^2}{54}\) respectively. We show that the constant \(-1/54\) is optimal under some additional conditions.