Minus domination in graphs

Jean Dunbar, Stephen Hedetniemi, Michael A. Henning, Alice McRae

Research output: Contribution to journalArticlepeer-review

46 Citations (Scopus)

Abstract

We introduce one of many classes of problems which can be defined in terms of 3-valued functions on the vertices of a graph G = (V,E) of the form f : V → {-1,0,1}. Such a function is said to be 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. For every graph G, γ-(G)≤γ(G) where γ(G) denotes the domination number of G. We show that if T is a tree of order n≥4, then γ(T)-γ-(T)≤(n-4)/5 and this bound is sharp. We attempt to classify graphs according to their minus domination numbers. For each integer n we determine the smallest order of a connected graph with minus domination number equal to n. Properties of the minus domination number of a graph are presented and a number of open questions are raised.

Original languageEnglish
Pages (from-to)35-47
Number of pages13
JournalDiscrete Mathematics
Volume199
Issue number1-3
DOIs
Publication statusPublished - 28 Mar 1999
Externally publishedYes

Keywords

  • Minus dominating function
  • Trees

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Minus domination in graphs'. Together they form a unique fingerprint.

Cite this