Nonnegative Signed Edge Domination in Graphs


N. Dehgardi, L. Volkmann




A nonnegative signed edge dominating function of a graph $G=(V, E)$ is a function $f: E\rightarrow \{-1,1\}$ such that $\sum_{e'\in N[e]}f(e')\ge 0$ for each $e\in E$, where $N[e]$ is the closed neighborhood of $e$. The weight of a nonnegative signed edge dominating function $f$ is $\omega(f)=\sum_{e\in E}f(e)$. The nonnegative signed edge domination number $\gamma_{ns}'(G)$ of $G$ is the minimum weight of a nonnegative signed edge dominating function of $G$. In this paper, we prove that for every tree $T$ of order $n\ge 3$, $1-\frac{n}{3}\le\gamma_{ns}'(T)\le\left\lfloor\frac{n-1}{3}\right\rfloor$. Also we present some sharp bounds for the nonnegative signed edge domination number. In addition, we determine the nonnegative signed edge domination number for the complete graph, and the complete bipartite graph $K_{n,n}$.