×

Roman \(\{2\}\)-domination problem in graphs. (English) Zbl 1485.05132

Summary: For a graph \(G = (V, E)\), a Roman \(\{2\}\)-dominating function (R2DF) \(f : V \rightarrow \{0, 1, 2\}\) has the property that for every vertex \(v \in V\) with \(f(v) = 0\), either there exists a neighbor \(u \in N(v)\), with \(f(u) = 2\), or at least two neighbors \(x, y \in N(v)\) having \(f(x) = f(y) = 1\). The weight of an R2DF \(f\) is the sum \(f (V) = \sum_{v \in V} f(v)\), and the minimum weight of an R2DF on \(G\) is the Roman \(\{2\}\)-domination number \(\gamma_{\{R2\}}(G)\). An R2DF is independent if the set of vertices having positive function values is an independent set. The independent Roman \(\{2\}\)-domination number \(i_{\{R2\}}(G)\) is the minimum weight of an independent Roman \(\{2\}\)-dominating function on \(G\). In this paper, we show that the decision problem associated with \(\gamma_{\{R2\}}(G)\) is NP-complete even when restricted to split graphs. We design a linear time algorithm for computing the value of \(i_{\{R2\}}(T)\) in any tree \(T\), which answers an open problem raised by A. Rahmouni and M. Chellali [Discrete Appl. Math. 236, 408–414 (2018; Zbl 1377.05145)]. Moreover, we present a linear time algorithm for computing the value of \(\gamma_{\{R2\}}(G)\) in any block graph \(G\), which is a generalization of trees.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)

Citations:

Zbl 1377.05145

References:

[1] E.W. Chambers, B. Kinnersley, N. Prince and D.B. West, Extremal problems for Roman domination, SIAM J. Discrete Math. 23 (2009) 1575-1586. doi:10.1137/070699688 · Zbl 1207.05135
[2] G.J. Chang, Algorithmic Aspects of Domination in Graphs (Handbook of Combinatorial Optimization, Kluwer Academic Pub., 1998).
[3] G.J. Chang, Total domination in block graphs, Oper. Res. Lett. 8 (1989) 53-57. doi:10.1016/0167-6377(89)90034-5 · Zbl 0678.90086
[4] M. Chellali, T.W. Haynes, S.T. Hedetniemi and A.A. McRae, Roman {2}-domination, Discrete Appl. Math. 204 (2016) 22-28. doi:10.1016/j.dam.2015.11.013 · Zbl 1333.05217
[5] L. Chen, C. Lu and Z. Zeng, Labelling algorithms for paired-domination problems in block and interval graphs, J. Comb. Optim. 19 (2010) 457-470. doi:10.1007/s10878-008-9177-6 · Zbl 1197.90336
[6] E.J. Cockayne, P.A. Dreyer Jr., S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11-22. doi:10.1016/j.disc.2003.06.004 · Zbl 1036.05034
[7] M. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Acad. Press, New York, 1980). · Zbl 0541.05054
[8] M.A. Henning and W.F. Klostermeyer, Italian domination in trees, Discrete Appl. Math. 217 (2017) 557-564. doi:10.1016/j.dam.2016.09.035 · Zbl 1358.05218
[9] C.H. Liu and G.J. Chang, Upper bounds on Roman domination numbers of graphs, Discrete Math. 312 (2012) 1386-1391. doi:10.1016/j.disc.2011.12.021 · Zbl 1237.05154
[10] D. Pradhan and A. Jha, On computing a minimum secure dominating set in block graphs, J. Comb. Optim. 35 (2018) 613-631. doi:10.1007/s10878-017-0197-y · Zbl 1386.05143
[11] A. Rahmouni and M. Chellali, Independent Roman {2}-domination in graphs, Discrete Appl. Math. 236 (2018) 408-414. doi:10.1016/j.dam.2017.10.028 · Zbl 1377.05145
[12] D.B. West, Introduction to Graph Theory (Prentice Hall, Upper Saddle River, 2001).
[13] T.V. Wimer, Linear Algorithms on k-Terminal Graphs, PhD Thesis (Clemson University, 1987). · Zbl 0669.05050
[14] G. Xu, L. Kang, E. Shan and M. Zhao, Power domination in block graphs, Theoret. Comput. Sci. 359 (2006) 299-305. doi:10.1016/j.tcs.2006.04.011 · Zbl 1098.05064
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.