DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

A. Poureidi

Abolfazl Poureidi

email: a.poureidi@gmail.com

N. Jafari Rad

Nader Jafari Rad

Department of Mathematics Shahrood Niversity of TechnologyUniversity Blvd. Shahrood IRAN

email: n.jafarirad@gmail.com

Title:

Algorithmic aspects of the independent 2-rainbow domination number and independent Roman $\{2\}$-domination number

PDF

Source:

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:

  1. 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
  2. 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
  3. 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
  4. M. Chellali and N. Jafari Rad, Independent $2$-rainbow domination in graphs, J. Combin. Math. Combin. Comput. 94 (2015) 133–148.
  5. M. Chellali and N. Jafari Rad, On $2$-rainbow domination and Roman domination in graphs, Australas. J. Combin. 56 (2013) 85–93.
  6. M. Chellali, T.W. Haynes, S.T. Hedetniemi and A. MacRae, Roman $\{2\}$-domination, Discrete Appl. Math. 204 (2016) 22–28..
  7. H. Chen and Ch. Lu, A note on Roman $\{2\}$-domination problem in graphs.
    arXiv: 1804.09338.pdf
  8. 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
  9. M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman, New York, 1979).
  10. T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).
  11. D. Lichtenstein, Planar formulae and their uses, SIAM J. Comput. 11 (1982) 329–343.
    https://doi.org/10.1137/0211025
  12. 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
  13. 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
  14. 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
  15. 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
  16. I. Stewart, Defend the Roman empire!, Sci. Amer. 281 (1999) 136–139.
    https://doi.org/10.1038/scientificamerican1299-136
  17. 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