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

Danila Cherkashin ; Pavel Prozorov

The electronic journal of combinatorics, Tome 29 (2022) no. 3

Résumé

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.

Détail

DOI : 10.37236/10500

Classification : 05C22, 05C69, 05C07
Mots-clés : signed edge domination function, signed graphon