An improved upper bound for signed edge domination numbers in graphs

The closed neighborhood N(G)[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 Sigma(x is an element of N[e]) f(x) >= 1 for each e is an element of E(G), then f is called a signed edge dominating function of G. The minimum of the values of Sigma(x is an element of E(G)) f (x), taken over every signed edge dominating function 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)'(G) <= n - 1 for every simple graph G of order n. In this paper we prove that this conjecture is true for Eulerian simple graphs, simple graphs with all vertices of odd degree and regular graphs. As a result we prove that for any simple graph G of order n, gamma(s)'(G) <= inverted right perpendicular3n/2inverted left perpendicular. This improves the previous upper bound left perpendicular11n/6 - 1right perpendicular.