Geodesic
Efficient $(j, k)$-dominating functions
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 115-135

Voir la notice de l'article provenant de la source Library of Science

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 lt; 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: efficient $(j,k)$-dominating function, efficient dominating set, $k$-tuple dominating set, strongly chordal graph, tree, complexity 
@article{DMGT_2023_43_1_a6,
     author = {Klostermeyer, William F. and MacGillivray, Gary and Semnani, Saeed Mohammadian and Piri, Farzaneh},
     title = {Efficient $(j, k)$-dominating functions},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {115--135},
     publisher = {mathdoc},
     volume = {43},
     number = {1},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a6/}
}
TY  - JOUR
AU  - Klostermeyer, William F.
AU  - MacGillivray, Gary
AU  - Semnani, Saeed Mohammadian
AU  - Piri, Farzaneh
TI  - Efficient $(j, k)$-dominating functions
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 115
EP  - 135
VL  - 43
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a6/
LA  - en
ID  - DMGT_2023_43_1_a6
ER  - 
%0 Journal Article
%A Klostermeyer, William F.
%A MacGillivray, Gary
%A Semnani, Saeed Mohammadian
%A Piri, Farzaneh
%T Efficient $(j, k)$-dominating functions
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 115-135
%V 43
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a6/
%G en
%F DMGT_2023_43_1_a6
Klostermeyer, William F.; MacGillivray, Gary; Semnani, Saeed Mohammadian; Piri, Farzaneh. Efficient $(j, k)$-dominating functions. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 115-135. http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a6/