Signed Edge Domination Numbers in Trees

Abstract

The closed neighborhood $N[e]$ of an edge $e$ in a graph $G$ is the set consisting of $e$ and of all edges having a common end-vertex with $e$. Let $f$ be a function on $E(G)$, the edge set of $G$, into the set $\{-1,1\}$. If $\sum _{e\in N[e]}f(x)\ge 1$ for each $e\in E(G)$, then $f$ is called a signed edge dominating function of $G$. The minimum of the values $\sum _{e\in E(G)}f(e)$, taken over all signed edge dominating functions $f$ of $G$, is called the signed edge domination number of $G$ and is denoted by ${\gamma }_s^{\prime }(G)$. It has been conjectured that ${\gamma }_s^{\prime }(T)\ge 1$ for every tree $T$. In this paper we prove that this conjecture is true and then classify all trees $T$ with ${\gamma }_s^{\prime }(T)=1,2$ and $3$.