THE ALGORITHMIC COMPLEXITY OF MINUS DOMINATION IN GRAPHS

A three-valued function f defined on the vertices of a graph G = (V,E) , f : V --> {-1,0,1}, is a minus dominating function if the sum of its function values over any closed neighborhood is at least one. That is , for every v epsilon V, f(N[v])greater than or equal to 1, where N[v] consists of v and every vertex adjacent to v. The weight of a minus d ominating function is f(V) = Sigma f(v), over all vertices v epsilon V . The minus domination number of a graph G, denoted gamma(-)(G), equal s the minimum weight of a minus dominating function of G, The upper mi nus domination number of a graph G, denoted Gamma(-)(G), equals the ma ximum weight of a minimal minus dominating function of G. In this pape r we present a variety of algorithmic results. We show that the decisi on problem corresponding to the problem of computing gamma(-) (respect ively, Gamma(-)) is NP-complete even when restricted to bipartite grap hs or chordal graphs. We also present a linear time algorithm for find ing a minimum minus dominating function in an arbitrary tree.