## Abstract

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 ∈ V, f(N[v]) ≥ 1, where N[v] consists of v and every vertex adjacent to v. The weight of a minus dominating function is f(V) = Σ f(v), over all vertices v ∈ V. The minus domination number of a graph G, denoted γ^{-}(G), equals the minimum weight of a minus dominating function of G. The upper minus domination number of a graph G, denoted Γ^{-}(G), equals the maximum weight of a minimal minus dominating function of G. In this paper we present a variety of algorithmic results. We show that the decision problem corresponding to the problem of computing γ^{-} (respectively, Γ^{-}) is NP-complete even when restricted to bipartite graphs or chordal graphs. We also present a linear time algorithm for finding a minimum minus dominating function in an arbitrary tree.

Original language | English |
---|---|

Pages (from-to) | 73-84 |

Number of pages | 12 |

Journal | Discrete Applied Mathematics |

Volume | 68 |

Issue number | 1-2 |

DOIs | |

Publication status | Published - 12 Jun 1996 |

Externally published | Yes |

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics