Article in volume
Authors:
Title:
Roman $\{2\}$-domination problem in graphs
PDFSource:
Discussiones Mathematicae Graph Theory 42(2) (2022) 641-660
Received: 2019-12-13 , Revised: 2020-05-18 , Accepted: 2020-05-20 , Available online: 2020-05-29 , https://doi.org/10.7151/dmgt.2332
Abstract:
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 Rahmouni and Chellali [Independent Roman $\{2\}$-domination in graphs, Discrete Appl. Math. 236 (2018) 408–414]. 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.
Keywords:
Roman $\{2\}$-domination, domination, algorithms
References:
- E.W. Chambers, B. Kinnersley, N. Prince and D.B. West, Extremal problems for Roman domination, SIAM J. Discrete Math. 23 (2009) 1575–1586.
https://doi.org/10.1137/070699688 - G.J. Chang, Algorithmic Aspects of Domination in Graphs (Handbook of Combinatorial Optimization, Kluwer Academic Pub., 1998).
- G.J. Chang, Total domination in block graphs, Oper. Res. Lett. 8 (1989) 53–57.
https://doi.org/10.1016/0167-6377(89)90034-5 - M. Chellali, T.W. Haynes, S.T. Hedetniemi and A.A. McRae, Roman $\{2\}$-domination, Discrete Appl. Math. 204 (2016) 22–28.
https://doi.org/10.1016/j.dam.2015.11.013 - 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.
https://doi.org/10.1007/s10878-008-9177-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.
https://doi.org/10.1016/j.disc.2003.06.004 - M. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Acad. Press, New York, 1980).
- M.A. Henning and W.F. Klostermeyer, Italian domination in trees, Discrete Appl. Math. 217 (2017) 557–564.
https://doi.org/10.1016/j.dam.2016.09.035 - C.H. Liu and G.J. Chang, Upper bounds on Roman domination numbers of graphs, Discrete Math. 312 (2012) 1386–1391.
https://doi.org/10.1016/j.disc.2011.12.021 - D. Pradhan and A. Jha, On computing a minimum secure dominating set in block graphs, J. Comb. Optim. 35 (2018) 613–631.
https://doi.org/10.1007/s10878-017-0197-y - A. Rahmouni and M. Chellali, Independent Roman $\{2\}$-domination in graphs, Discrete Appl. Math. 236 (2018) 408–414.
https://doi.org/10.1016/j.dam.2017.10.028 - D.B. West, Introduction to Graph Theory (Prentice Hall, Upper Saddle River, 2001).
- T.V. Wimer, Linear Algorithms on $k$-Terminal Graphs, PhD Thesis (Clemson University, 1987).
- G. Xu, L. Kang, E. Shan and M. Zhao, Power domination in block graphs, Theoret. Comput. Sci. 359 (2006) 299–305.
https://doi.org/10.1016/j.tcs.2006.04.011
Close