Minus domination in graphs
type: Item
instance of: scholarly article
title: Minus domination in graphs
zbMATH Open document ID: 0928.05046
DOI: 10.1016/S0012-365X(98)00284-2
author: Michael A. Henning
author: Jean E. Dunbar
author: Stephen T. Hedetniemi
author: Alice A. McRae
published in: Discrete Mathematics
publication date: 2000-01-09T00:00:00Z
review text: Let \(G\) be a graph with vertex set \(V\). A function \(f: V\to\{-1,0,1\}\) is called a minus dominating function on \(G\), if the sum of its values over the closed neighbourhood \(N[v]\) of an arbitrary vertex \(v\in V\) is at least 1. The weight \(w(f)\) is defined by \(\sum_{x\in V}f(x)\). The minimum of \(w(f)\) taken over all minus dominating functions \(f\) on \(G\) is called the minus domination number \(\gamma^-(G)\) of \(G\). If the set \(\{0,1\}\) is used instead of \(\{-1,0,1\}\), then we have the definition of the domination number \(\gamma(G)\) of \(G\). In the paper it is proved that \(\gamma(G)- \gamma^-(T)\leq (n-4)/5\) for every tree \(T\) with \(n\geq 4\) vertices. There exist outerplanar graphs, chordal graphs and bipartite graphs with \(\gamma^-(G)\) arbitrarily small. If the degrees of the vertices do not exceed 5, then \(\gamma^-(G)\) is nonnegative. At the end the minimum number \(p(n,\gamma^-)\) of vertices of a graph with \(n\) vertices and with the minus domination number \(\gamma^-\) is studied.
reviewed by: Bohdan Zelinka
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1321790
zbMATH Keywords: minus dominating function
zbMATH Keywords: minus domination number
zbMATH Keywords: trees
MaRDI profile type: Publication
cites work: Q4350166
cites work: Contributions to the theory of domination, independence and irredundance in graphs
cites work: Properties of Hereditary Hypergraphs and Middle Graphs
cites work: Q4014312
cites work: Q5753985
cites work: The algorithmic complexity of minus domination in graphs
cites work: Minus domination in regular graphs
cites work: Domination, Fractional Domination, 2-Packing, and Graph Products
cites work: Fractional domination of strong direct products
cites work: Q4368728
cites work: Q4368729
cites work: Chordal graphs and upper irredundance, upper domination and independence
full work available at URL: s0012-365x(98)00284-2
OpenAlex ID: W2020597434
description: scientific article; zbMATH DE number 1321790