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

Danila Cherkashin, Pavel Prozorov

Published 2020-12-17Version 1

We show that the minimal sum of edges in a signed edge-dominated graph with $n$ vertices is at least $-\frac{n^2}{25}$. Also we provide an example of a signed edge-dominated graph with $n$ vertices with the sum of edges $-(1+o(1))\frac{n^2}{8(1 + \sqrt{2})^2}$.