Discussiones Mathematicae Graph Theory (Feb 2023)

Efficient (j, k)-Dominating Functions

  • Klostermeyer William F.,
  • MacGillivray Gary,
  • Semnani Saeed Mohammadian,
  • Piri Farzaneh

DOI
https://doi.org/10.7151/dmgt.2355
Journal volume & issue
Vol. 43, no. 1
pp. 115 – 135

Abstract

Read online

For positive integers j and k, an efficient (j, k)-dominating function of a graph G = (V, E) is a function f : V → {0, 1, 2, . . ., j} such that the sum of function values in the closed neighbourhood of every vertex equals k. The relationship between the existence of efficient (j, k)-dominating functions and various kinds of efficient dominating sets is explored. It is shown that if a strongly chordal graph has an efficient (j, k)-dominating function, then it has an efficient dominating set. Further, every efficient (j, k)-dominating function of a strongly chordal graph can be expressed as a sum of characteristic functions of efficient dominating sets. For j < k there are strongly chordal graphs with an efficient dominating set but no efficient (j, k)-dominating function. The problem of deciding whether a given graph has an efficient (j, k)-dominating function is shown to be NP-complete for all positive integers j and k, and solvable in polynomial time for strongly chordal graphs when j = k. By taking j = 1 we obtain NP-completeness of the problem of deciding whether a given graph has an efficient k-tuple dominating set for any fixed positive integer k. Finally, we consider efficient (2, 2)-dominating functions of trees. We describe a new constructive characterization of the trees with an efficient dominating set and a constructive characterization of the trees with two different efficient dominating sets. A number of open problems and questions are stated throughout the work.

Keywords