Geodesic
Efficient $(j, k)$-dominating functions
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 115-135 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2023},
     volume = {43},
     number = {1},
     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
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
%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/

[1] R.P. Anstee and M. Farber, Characterizations of totally balanced matrices, J. Algorithms 5 (1984) 215–230. https://doi.org/10.1016/0196-6774(84)90028-2

[2] D.W. Bange, A.E. Barkauskas and P.J. Slater, Efficient dominating sets in graphs, in: Applications of Discrete Mathematics, R.D. Ringeisen, F.S. Roberts (Ed(s)), (SIAM, Philadelphia, PA 1988) 189–199.

[3] N. Biggs, Perfect codes in graphs, J. Combin. Theory Ser. B 15 (1973) 289–296. https://doi.org/10.1016/0095-8956(73)90042-7

[4] A. Brandstädt, A. Leitert and D. Rautenbach, Efficient dominating and edge dominating sets for graphs and hypergraphs, in: Algorithms and Computation, Lecture Notes in Comput. Sci. 7676 (2012) 267–277. https://doi.org/10.1007/978-3-642-35261-4_30

[5] G.J. Chang and G.L. Nemhauser, The k-domination and k-stability problems on sun-free chordal graphs, SIAM J. Algebraic Discrete Methods 5 (1984) 332–345. https://doi.org/10.1137/0605034

[6] M. Chellali, A. Khelladi and F. Maffray, Exact double domination in graphs, Discuss. Math. Graph Theory 25 (2005) 291–302. https://doi.org/10.7151/dmgt.1282

[7] T.J. Schaefer, The complexity of satisfiability problems, Proceedings of the 10th Annual ACM Symposium on Theory of Computing (1978) 216–226. https://doi.org/10.1145/800133.804350

[8] M. Farber, Domination, independent domination, and duality in strongly chordal graphs, Discrete Appl. Math. 7 (1984) 115–130. https://doi.org/10.1016/0166-218X(84)90061-1

[9] M. Farber, Characterizations of strongly chordal graphs, Discrete Math. 43 (1983) 173–189. https://doi.org/10.1016/0012-365X(83)90154-1

[10] D.R. Fulkerson, A. Hoffman and R. Oppenheim, On balanced matrices, Math. Program. Study 1 (1974) 120–132. https://doi.org/10.1007/BFb0121244

[11] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H Freeman and Co, New York, 1979).

[12] G. Gunther, B. Hartnell, L.R. Markus and D.F. Rall, Graphs with unique minimum dominating sets, Congr. Numer. 101 (1994) 55–63.

[13] M.A. Henning and W. Klostermeyer, Italian domination in trees, Discrete Appl. Math. 217 (2017) 557–564. https://doi.org/10.1016/j.dam.2016.09.035

[14] F. Harary and T.W. Haynes, The k-tuple domatic number of a graph, Math. Slovaca 48 (1998) 161–166.

[15] F. Harary and T.W. Haynes, Double domination in graphs, Ars Combin. 55 (2000) 201–213.

[16] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). https://doi.org/10.1201/9781482246582

[17] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998). https://doi.org/10.1201/9781315141428

[18] T.W. Haynes and M.A. Henning, Perfect Italian domination in trees, Discrete Appl. Math. 260 (2019) 164–177. https://doi.org/10.1016/j.dam.2019.01.038

[19] W.F. Klostermeyer and G. MacGillivray, Roman, Italian, and 2-domination, J. Combin. Math. Combin. Comput. 108 (2019) 125–146.

[20] M. Livingston and Q.J. Stout, Perfect dominating sets, Congr. Numer. 79 (1990) 187–203.

[21] R.R Rubalcaba and P.J. Slater, Efficient (j,k)-domination, Discuss. Math. Graph Theory 27 (2007) 409–423. https://doi.org/10.7151/dmgt.1371

[22] C.C. Yen and R.C.T. Lee, The weighted perfect domination problem and its variants, Discrete Appl. Math. 66 (1996) 147–160. https://doi.org/10.1016/0166-218X(94)00138-4