Weak Roman domination in rooted product graphs

Rangel Hernández-Ortiz; Luis Pedro Montejano; Juan Alberto Rodríguez-Velázquez; Rangel Hernández-Ortiz; Luis Pedro Montejano; Juan Alberto Rodríguez-Velázquez

doi:10.3934/math.2021217

AIMS Mathematics

2021, Volume 6, Issue 4: 3641-3653. doi: 10.3934/math.2021217

Previous Article Next Article

Research article

Weak Roman domination in rooted product graphs

Rangel Hernández-Ortiz ¹,
Luis Pedro Montejano ²,
Juan Alberto Rodríguez-Velázquez ^{3
,
,}

1.
Universidad Autónoma Metropolitana, Departamento de Matemáticas Aplicadas y Sistemas, Ciudad de México, Mexico
2.
Serra Húnter Fellow, Universitat Rovira i Virgili, Departament d'Enginyeria Informàtica i Matemàtiques, Av. Països Catalans 26, 43007 Tarragona, Spain
3.
Universitat Rovira i Virgili, Departament d'Enginyeria Informàtica i Matemàtiques, Av. Països Catalans 26, 43007 Tarragona, Spain

Received: 11 September 2020 Accepted: 11 January 2021 Published: 22 January 2021
MSC : 05C69, 05C76

In this paper, we obtain closed formulae for the weak Roman domination number of rooted product graphs. As a consequence of the study, we show that the use of rooted product graphs is a useful tool to show that the problem of computing the weak Roman domination number of a graph is NP-hard.
- weak Roman domination,
- NP-hard,
- rooted product graphs,
- corona product graphs,
- protection of graphs
Citation: Rangel Hernández-Ortiz, Luis Pedro Montejano, Juan Alberto Rodríguez-Velázquez. Weak Roman domination in rooted product graphs[J]. AIMS Mathematics, 2021, 6(4): 3641-3653. doi: 10.3934/math.2021217

Related Papers:

Abstract

In this paper, we obtain closed formulae for the weak Roman domination number of rooted product graphs. As a consequence of the study, we show that the use of rooted product graphs is a useful tool to show that the problem of computing the weak Roman domination number of a graph is NP-hard.

References

[1]	A. Cabrera Martínez, L. P. Montejano, J. A. Rodríguez-Velázquez, Total weak Roman domination in graphs, Symmetry, 11 (2019), 831. doi: 10.3390/sym11060831
[2]	A. Cabrera-Martínez, I. G. Yero, Constructive characterizations concerning weak Roman domination in trees, Discrete Appl. Math., 284 (2020), 384–390. doi: 10.1016/j.dam.2020.03.058
[3]	M. Chellali, T. W. Haynes, S. T. Hedetniemi, Bounds on weak Roman and 2-rainbow domination numbers, Discrete Appl. Math., 178 (2014), 27–32. doi: 10.1016/j.dam.2014.06.016
[4]	E. J. Cockayne, O. Favaron, C. M. Mynhardt, Secure domination, weak Roman domination and forbidden subgraphs, Bull. Inst. Combin. Appl., 39 (2003), 87–100.
[5]	E. J. Cockayne, P. J. P. Grobler, W. R. Gründlingh, J. Munganga, J. H. van Vuuren, Protection of a graph, utilitas mathematica, 67 (2005), 19–32.
[6]	M. Dettlaff, M. Lemańska, J. A. Rodríguez-Velázquez, R. Zuazua, On the super domination number of lexicographic product graphs, Discrete Appl. Math., 263 (2019), 118–129. doi: 10.1016/j.dam.2018.03.082
[7]	H. Fernau, J. A. Rodríguez-Velázquez, On the (adjacency) metric dimension of corona and strong product graphs and their local variants: Combinatorial and computational results, Discrete Appl. Math., 236 (2018), 183–202. doi: 10.1016/j.dam.2017.11.019
[8]	H. Fernau, J. A. Rodríguez-Velázquez, Notions of metric dimension of corona products: combinatorial and computational results, In: Computer science-theory and applications, Springer, Cham, 2014.
[9]	M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, USA, 1979.
[10]	T. Haynes, S. Hedetniemi, P. Slater, Domination in Graphs: Advanced Topics, CRC Press, 1998.
[11]	T. Haynes, S. Hedetniemi, P. Slater, Fundamentals of Domination in Graphs, CRC Press, 1998.
[12]	M. A. Henning, S. T. Hedetniemi, Defending the Roman Empire-a new strategy, Discrete Math., 266 (2003), 239–251. doi: 10.1016/S0012-365X(02)00811-7
[13]	M. Ivanović, D. Urošević, Variable neighborhood search approach for solving Roman and weak Roman domination problems on graphs, Comput. Inform., 38 (2019), 57–84. doi: 10.31577/cai_2019_1_57
[14]	P. Roushini Leely Pushpam, T. N. M. Malini Mai, Weak roman domination in graphs, Discuss. Math. Graph T., 31 (2011), 161–170. doi: 10.7151/dmgt.1535
[15]	P. Roushini Leely Pushpam, M. Kamalam, Effect of vertex deletion on the weak Roman domination number of a graph, AKCE Int. J. Graphs Comb., 16 (2019), 204–212. doi: 10.1016/j.akcej.2017.12.003
[16]	D. Klein, J. A. Rodríguez-Velázquez, Protection of lexicographic product graphs, Discuss. Math. Graph Theory, https://doi.org/10.7151/dmgt.2243.
[17]	M. Valveny, H. Pérez-Rosés, J. A. Rodríguez-Velázquez, On the weak Roman domination number of lexicographic product graphs, Discrete Appl. Math., 263 (2019), 257–270. doi: 10.1016/j.dam.2018.03.039
[18]	M. Valveny, J. A. Rodríguez-Velázquez, Protection of graphs with emphasis on Cartesian product graphs, Filomat, 33 (2019), 319–333. doi: 10.2298/FIL1901319V

Reader Comments

Your name:*

Email:*
© 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)