Journal Details
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Open Access

Efficient (j, k)-Dominating Functions

Accepted: 25 Jul 2020
Journal Details
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English

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.

MSC 2010

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

[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.Search in Google Scholar

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

[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. doi:10.1007/978-3-642-35261-4_3010.1007/978-3-642-35261-4_30Search in Google Scholar

[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. doi:10.1137/060503410.1137/0605034Search in Google Scholar

[6] M. Chellali, A. Khelladi and F. Ma ray, Exact double domination in graphs, Discuss. Math. Graph Theory 25 (2005) 291–302. doi:10.7151/dmgt.128210.7151/dmgt.1282Search in Google Scholar

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

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

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

[10] D.R. Fulkerson, A. Hoffman and R. Oppenheim, On balanced matrices, Math. Program. Study 1 (1974) 120–132. doi:10.1007/BFb012124410.1007/BFb0121244Search in Google Scholar

[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).Search in Google Scholar

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

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

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

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

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

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

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

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

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

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

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

• A Note About Monochromatic Components in Graphs of Large Minimum Degree

Recommended articles from Trend MD