On signed edge domination numbers of graphs (Q5946759): Difference between revisions

A function \(f:E\to\{ -1,1\}\) on the edge set of a graph \(G=(V,E)\) is a signed edge domination function, if \(\sum_{e'\in N[e]}f(e')\geq 1\) for each \(e\in E\) where the set \(N[e]\) consists of \(e\) and all edges incident with \(e\). The author proves that the minimum weight \(\sum_{e\in E}f(e)\) of a signed edge domination function \(f\), i.e. the so-called signed domination number \(\gamma_s'(G)\), of a graph \(G\) with \(m\) edges is at least \(2\lceil\frac{1}{3} \lceil\frac{\sqrt{24m+25}+6m+5}{6}\rceil\rceil-m\). Furthermore, he proves that \(\gamma_s'(G)=|E|\) if and only if \(G\) is a path \(P_n\) for \(2\leq n\leq 5\) or arises from a star \(K_{1,n}\) for \(n\geq 3\) by subdividing each edge once.