Upper bounds on the signed edge domination number of a graph (Q2214050)

A signed edge domination function of a graph \(G=(V(G), E(G))\) is a function \(f:E(G)\rightarrow \{-1,1\}\) such that \(\sum_{e^\prime\in N[e]}f(e^\prime) \ge 1\) holds for every edge \(e\in E(G)\). The signed edge domination number \(\gamma_s^\prime(G)\) of \(G\) is the minimum value of a signed edge domination function of \(G\). It was conjectured that if \(G\) is a graph of order \(n\), then \(\gamma_s^\prime(G) \le n-1\). In this paper, it is proved that the conjecture holds if \(G\) has precisely one or two even vertices. It is also proved that if \(G\) is a graph of order \(n\), then \(\gamma_s^\prime(G) \le (4n-2)/3\). This improves the best previous general upper bound on \(\gamma_s(G)\).