A Note on Roman \{2\}-domination problem in graphs

MaRDI QIDQ6300771zbMATH OpenFDO

Authors Hangdi Chen, Changhong Lu

Publication date 25 April 2018

Abstract: For a graph $G=(V,E)$, a Roman $2$-dominating function (R2DF)$f:Vightarrow0,1,2$ has the property that for every vertex $vinV$ with $f(v)=0$, either there exists a neighbor $uinN(v)$, with $f(u)=2$, or at least two neighbors $x,yinN(v)$ having $f(x)=f(y)=1$. The weight of a R2DF is the sum $f(V)=su{m}_{vinV}f(v)$, and the minimum weight of a R2DF is the Roman $2$-domination number $gamm{a}_{R2}(G)$. A 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 $gamm{a}_{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)$ for any tree $T$. This answers an open problem raised by Rahmouni and Chellali [Independent Roman $2$-domination in graphs, Discrete Applied Mathematics 236 (2018), 408-414]. Chellali, Haynes, Hedetniemi and McRae cite{chellali2016roman} have showed that Roman $2$-domination number can be computed for the class of trees in linear time. As a generalization, we present a linear time algorithm for solving the Roman $2$-domination problem in block graphs.

This page was built for publication: A Note on Roman \{2\}-domination problem in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6300771)