论文标题
在签名的边缘主导的图中的边缘总和最少
On the minimal sum of edges in a signed edge-dominated graph
论文作者
论文摘要
让$ g $是一个简单的图形，带有$ n $顶点和$ \ pm 1 $ - 边缘的$ weights。假设对于每个边缘$ e $，$ e $（包括$ e $）的边缘总和为正。然后，$ g $的边缘的权重总和至少为$ - \ frac {n^2} {25} $。另外，我们提供了一个加权图的示例，具有所描述的属性和权重总和$ - （1 + o（1））\ frac {n^2} {8（1 + \ sqrt {2}）^2} $。 以前最著名的边界是$ - \ frac {n^2} {16} $和$ - （1+o（1））\ frac {n^2} {54} $。我们表明，在某些其他条件下，常量$ -1/54 $是最佳的。
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.
