Efficient minus and signed domination in graphs (Journal)

[[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 summation u is a member of the set of N[v] f(u) = 1 for all v is a member of the set of V, where N[v] = {v} [union] {u|(u, v) is a member of the set of 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.[[fileno]]2030209010020[[department]]資訊工程學