Signed Edge Domination Number of Interval Graphs

Let G=(V,E) be an undirected graph with vertex set V and edge set E. The open neighborhood N(e) of an edge e∈E is the set of all edges adjacent to e. The closed neighborhood of e is denoted by N[e] and N[e]=N(e)∪{e}. A function f:E→{1,−1} is said to be a signed edge dominating function (SEDF), if f satisfies the condition ∑e′∈N[e]f(e′)≥1 for every e∈E. The minimum of the values of ∑e∈Ef(e), taken over all signed edge dominating functions f on G, is called the signed edge domination number (SEDN) of G and is denoted by γs′(G). In this paper, an O(n2) time algorithm is designed to compute the signed edge domination number of interval graphs.