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) \geq 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(G)\). It has been conjectured that \(\gamma’_s(T) \geq 1\) for every tree \(T\). In this paper we prove that this conjecture is true and then classify all trees \(T\) with \(\gamma’_s(T) = 1,2\) and \(3\).