Abstract
An efficient minus (respectively, signed) dominating function of a graph G = (V, E) is a function f:V → {-1, 0, 1} (respectively, {-1, 1}) such that ∑ u∈N[v] f(u) = 1 for all v ∈ V, where N[v] = {v} ∪ {u|(u, v) ∈ E}. The efficient minus (respectively, signed) domination problem is to find an efficient minus (respectively, signed) dominating function of G. In this paper, we show that the efficient minus (respectively, signed) domination problem is NP-complete on chordal graphs, chordal bipartite graphs, planar bipartite graphs and planar graphs of maximum degree 4 (respectively, on chordal graphs). Based on the forcing property on blocks of vertices and automata theory, we provide a uniform approach to show that in a special class of interval graphs, every graph (respectively, every graph with no vertex of odd degree) has an efficient minus (respectively, signed) dominating function. We also give linear-time algorithms to find these functions. Besides, we show that the efficient minus domination problem is equivalent to the efficient domination problem on trees. © 2002 Elsevier Science B.V. All rights reserved.