Article in volume
Authors:
Title:
Algorithmic aspects of the independent 2-rainbow domination number and independent Roman $\{2\}$-domination number
PDFSource:
Discussiones Mathematicae Graph Theory 42(3) (2022) 709-726
Received: 2019-02-27 , Revised: 2019-12-21 , Accepted: 2019-12-24 , Available online: 2020-01-31 , https://doi.org/10.7151/dmgt.2299
Abstract:
A 2-rainbow dominating function (2RDF) of a graph $G$ is a function $g$ from the vertex set $V(G)$ to the family of all subsets of $\{1,2\}$ such that
for each vertex $v$ with $g(v) =\emptyset$ we have $\bigcup_{u\in N(v)}g(u) =
\{1,2\}$. The minimum of $g(V (G))=\sum_{v\in V(G)}|g(v)|$ over all such
functions is called the 2-rainbow domination number. A 2RDF $g$ of a graph $G$
is independent if no two vertices assigned non empty sets are adjacent. The
independent 2-rainbow domination number is the minimum weight of an
independent 2RDF of $G$. A Roman $\{2\}$-dominating function (R2DF)
$f:V\longrightarrow\{0,1,2\}$ of a graph $G=(V, E)$ has the property that for
every vertex $v\in V$ with $f(v)=0$ either there is $u\in N(v)$ with $f(u)=2$
or there are $x,y\in N(v)$ with $f(x)=f(y)=1$. The weight of $f$ is the sum
$f(V)=\sum_{v\in V}f (v)$. An R2DF $f$ is called independent if no two vertices
assigned non-zero values are adjacent. The independent Roman $\{2\}$-domination
number is the minimum weight of an independent R2DF on $G$.
We first show that the decision problem for computing the independent 2-rainbow
(respectively, independent Roman $\{2\}$-domination) number is NP-complete even
when restricted to planar graphs. Then, we give a linear algorithm that computes
the independent 2-rainbow domination number as well as the independent Roman
$\{2\}$-domination number of a given tree, answering problems posed in
[M. Chellali and N. Jafari Rad, Independent $2$-rainbow domination in graphs,
J. Combin. Math. Combin. Comput. 94 (2015) 133–148] and [A. Rahmouni and
M. Chellali, Independent Roman $\{2\}$-domination in graphs, Discrete Appl.
Math. 236 (2018) 408–414]. Then, we give a linear algorithm that
computes the independent 2-rainbow domination number of a given unicyclic graph.
Keywords:
independent 2-rainbow dominating function, independent Roman $\{2\}$-dominating function, algorithm, 3-SAT
References:
- J. Amjadi, M. Falahat, N. Jafari Rad and S.M. Sheikholeslami, Strong equality between the $2$-rainbow domination and independent $2$-rainbow domination numbers in trees, Bull. Malays. Math. Sci. Soc. 39 (2016) 205–218.
https://doi.org/10.1007/s40840-015-0284-0 - B. Brešar, M.A. Henning and D.F. Rall, Rainbow domination in graphs, Taiwanese J. Math. 12 (2008) 213–225.
https://doi.org/10.11650/twjm/1500602498 - B. Brešar and T.K. Šumenjak, On the $2$-rainbow domination in graphs, Discrete Appl. Math. 155 (2007) 2394–2400.
https://doi.org/10.1016/j.dam.2007.07.018 - M. Chellali and N. Jafari Rad, Independent $2$-rainbow domination in graphs, J. Combin. Math. Combin. Comput. 94 (2015) 133–148.
- M. Chellali and N. Jafari Rad, On $2$-rainbow domination and Roman domination in graphs, Australas. J. Combin. 56 (2013) 85–93.
- M. Chellali, T.W. Haynes, S.T. Hedetniemi and A. MacRae, Roman $\{2\}$-domination, Discrete Appl. Math. 204 (2016) 22–28..
- H. Chen and Ch. Lu, A note on Roman $\{2\}$-domination problem in graphs.
arXiv: 1804.09338.pdf - E.J. Cockayane, P.M. 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.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman, New York, 1979).
- T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).
- D. Lichtenstein, Planar formulae and their uses, SIAM J. Comput. 11 (1982) 329–343.
https://doi.org/10.1137/0211025 - 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 - C.S. ReVelle and K.E. Rosing, Defendens imperium Romanum: A classical problem in military strategy, Amer. Math. Monthly 107 (2000) 585–594.
https://doi.org/10.1080/00029890.2000.12005243 - Z. Shao, Z. Li, A. Peperko, J. Wan and J. Žerovnik, Independent rainbow domination of graphs, Bull. Malays. Math. Sci. Soc. 42 (2019) 417–435.
https://doi.org/10.1007/s40840-017-0488-6 - Z. Shao, M. Liang, C. Yin, X. Xu, P. Pavlič and J. Žerovnik, On rainbow domination numbers of graphs, Inform. Sci. 254 (2014) 225–234.
https://doi.org/10.1016/j.ins.2013.07.020 - I. Stewart, Defend the Roman empire!, Sci. Amer. 281 (1999) 136–139.
https://doi.org/10.1038/scientificamerican1299-136 - Y. Wu and N. Jafari Rad, Bounds on the $2$-rainbow domination number of graphs, Graphs Combin. 29 (2013) 1125–1133.
https://doi.org/10.1007/s00373-012-1158-y
Close