Mixed double Roman domination in graphs

Articles in Press

Document Type : Original paper

Authors

1 Department of Mathematics, Babol Noshirvani University of Technology, Shariati Ave., Babol, I.R. Iran, Postal Code: 47148-71167

2 LAMDA-RO Laboratory, Department of Mathematics, University of Blida, Blida, Algeria

3 Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, Iran

4 Department of Mathematics, University of Cádiz, Spain

Abstract

Let $G=(V,E)$ be a simple graph with vertex set $V$ and edge set $E$. A mixed double Roman dominating function (MDRDF) of $G$ is a function $f:V\cup E \rightarrow \{0,1,2,3\}$ satisfying  (1) for any element $x\in V\cup E$ with $f(x)=0$, there must be either element $y\in V\cup E$, with $f(y)=3,$  which is adjacent or incident to $x$, or either two elements $y,z \in V\cup E$, with $f(y),f(z)=2$ which are adjacent or incident to $x$; (2) for any element $x\in V\cup E$ with $f(x)=1$, there must be either  element $y\in V\cup E$, with $f(y)\ge 2,$  which is adjacent or incident to $x$. The weight of an MDRDF $f$ is $w(f)=f(V\cup E)=\sum_{x\in V\cup E} f(x)$ and the minimum weight among all the MDRD functions the \textit{MDRD-number}, $\gamma _{dR}^*(G)$, of the graph $G$. In this paper we start the study of this variation of the classic Roman domination problem by setting some basic results, giving exact values and sharp bounds of the MDRD number and we approach the study of the complexity of the decision problem associated to the MDR domination in graphs. 

Keywords

Main Subjects

References

[1] H. Abdollahzadeh Ahangar, T.W. Haynes, and J.C. Valenzuela-Tripodoro, Mixed Roman domination in graphs, Bull. Malays. Math. Sci. Soc. 40 (2017), no. 4, 1443–1454.
https://doi.org/10.1007/s40840-015-0141-1
[2] H. Abdollahzadeh Ahangar, M.A. Henning, V. Samodivkin, and I.G. Yero, Total Roman domination in graphs, Appl. Anal. Discrete Math. 10 (2016), no. 2, 501–517.
[3] M.P. Alvarez-Ruiz, T. Mediavilla-Gradolph, S.M. Sheikholeslami, J.C. Valenzuela-Tripodoro, and I.G. Yero, On the strong Roman domination number of graphs, Discrete Appl. Math. 231 (2017), 44–59.
https://doi.org/10.1016/j.dam.2016.12.013
[4] R.A. Beeler, T.W. Haynes, and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23–29.
https://doi.org/10.1016/j.dam.2016.03.017
[5] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Roman domination in graphs, Topics in Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer International Publishing, Cham, 2020,
pp. 365–409.
[6] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Comb. 17 (2020), no. 3, 966–984.
https://doi.org/10.1016/j.akcej.2019.12.001
[7] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of roman domination, Structures of Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer International Publishing, Cham, 2021, pp. 273–307.
[8] X. Chen, A note on the double Roman domination number of graphs, Czechoslovak Math. J. 70 (2020), no. 1, 205–212.
https://doi.org/10.21136/CMJ.2019.0212-18
[9] E.J. Cockayne, P.A. Dreyer Jr, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), no. 1-3, 11–22.
https://doi.org/10.1016/j.disc.2003.06.004
[10] B. Courcelle, J.A. Makowsky, and U. Rotics, Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Syst. 33 (2000), no. 2, 125–150.
https://doi.org/10.1007/s002249910009
[11] N. Dehgardi, Mixed Roman domination and 2-independence in trees, Commun. Comb. Optim. 3 (2018), no. 1, 79–91.
https://doi.org/10.22049/cco.2018.25964.1062
[12] G. Hickey, F. Dehne, A. Rau-Chaplin, and C. Blouin, SPR distance computation for unrooted trees, Evol. Bioinform. 4 (2008), 17–27.
https://doi.org/10.4137/EBO.S419
[13] R. Khoeilar, H. Karami, M. Chellali, and S.M. Sheikholeslami, An improved upper bound on the double Roman domination number of graphs with minimum degree at least two, Discrete Appl. Math. 270 (2019), 159–167.
https://doi.org/10.1016/j.dam.2019.06.018
[14] M. Liedloff, T. Kloks, J. Liu, and S.L. Peng, Efficient algorithms for Roman domination on some classes of graphs, Discrete Appl. Math. 156 (2008), no. 18, 3400–3415.
https://doi.org/10.1016/j.dam.2008.01.011
[15] C.S. ReVelle and K.E. Rosing, Defendens imperium romanum: a classical problem in military strategy, Am. Math. Mon. 107 (2000), no. 7, 585–594.
https://doi.org/10.1080/00029890.2000.12005243
[16] I. Stewart, Defend the Roman empire!, Sci. Am. 281 (1999), no. 6, 136–138. 
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 22 August 2024

Files

Share

How to cite

Statistics