Article in volume
Authors:
Title:
Efficient $(j, k)$-dominating functions
PDFSource:
Discussiones Mathematicae Graph Theory 43(1) (2023) 115-135
Received: 2019-04-18 , Revised: 2020-07-22 , Accepted: 2020-07-25 , Available online: 2020-09-09 , https://doi.org/10.7151/dmgt.2355
Abstract:
For positive integers $j$ and $k$, an efficient $(j, k)$-dominating
function of a graph $G=(V,E)$ is a function $f: V \to \{0, 1, 2, \ldots, 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:
efficient $(j,k)$-dominating function, efficient dominating set, $k$-tuple dominating set, strongly chordal graph, tree, complexity
References:
- 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 - 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.
- 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 - 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 - 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 - 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 - T.J. Schaefer, The complexity of satisfiability problems, Proceedings of the $10^{th}$ Annual ACM Symposium on Theory of Computing (1978) 216–226.
https://doi.org/10.1145/800133.804350 - 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 - M. Farber, Characterizations of strongly chordal graphs, Discrete Math. 43 (1983) 173–189.
https://doi.org/10.1016/0012-365X(83)90154-1 - D.R. Fulkerson, A. Hoffman and R. Oppenheim, On balanced matrices, Math. Program. Study 1 (1974) 120–132.
https://doi.org/10.1007/BFb0121244 - 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).
- G. Gunther, B. Hartnell, L.R. Markus and D.F. Rall, Graphs with unique minimum dominating sets, Congr. Numer. 101 (1994) 55–63.
- 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 - F. Harary and T.W. Haynes, The $k$-tuple domatic number of a graph, Math. Slovaca 48 (1998) 161–166.
- F. Harary and T.W. Haynes, Double domination in graphs, Ars Combin. 55 (2000) 201–213.
- 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 - 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 - 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 - W.F. Klostermeyer and G. MacGillivray, Roman, Italian, and $2$-domination, J. Combin. Math. Combin. Comput. 108 (2019) 125–146.
- M. Livingston and Q.J. Stout, Perfect dominating sets, Congr. Numer. 79 (1990) 187–203.
- 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 - 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
Close