Roman domination in direct product graphs and rooted product graphs

Abel Cabrera Martínez; Iztok Peterin; Ismael G. Yero; Abel Cabrera Martínez; Iztok Peterin; Ismael G. Yero

doi:10.3934/math.2021643

AIMS Mathematics

2021, Volume 6, Issue 10: 11084-11096. doi: 10.3934/math.2021643

Previous Article Next Article

Research article

Roman domination in direct product graphs and rooted product graphs

1.
Universitat Rovira i Virgili, Departament d'Enginyeria Informàtica i Matemàtiques, Spain
2.
University of Maribor, Faculty of Electrical Engineering and Computer Science, Slovenia
3.
IMFM, Jadranska 19, 1000 Ljubljana, Slovenia
4.
Universidad de Cádiz, Departamento de Matemáticas, Escuela Politécnica Superior de Algeciras, Spain

Received: 20 May 2021 Accepted: 26 July 2021 Published: 02 August 2021
MSC : 05C69, 05C76

Let $ G $ be a graph with vertex set $ V(G) $. A function $ f:V(G)\rightarrow \{0, 1, 2\} $ is a Roman dominating function on $ G $ if every vertex $ v\in V(G) $ for which $ f(v) = 0 $ is adjacent to at least one vertex $ u\in V(G) $ such that $ f(u) = 2 $. The Roman domination number of $ G $ is the minimum weight $ \omega(f) = \sum_{x\in V(G)}f(x) $ among all Roman dominating functions $ f $ on $ G $. In this article we study the Roman domination number of direct product graphs and rooted product graphs. Specifically, we give several tight lower and upper bounds for the Roman domination number of direct product graphs involving some parameters of the factors, which include the domination, (total) Roman domination, and packing numbers among others. On the other hand, we prove that the Roman domination number of rooted product graphs can attain only three possible values, which depend on the order, the domination number, and the Roman domination number of the factors in the product. In addition, theoretical characterizations of the classes of rooted product graphs achieving each of these three possible values are given.
- roman domination,
- domination,
- direct product graph,
- rooted product graph
Citation: Abel Cabrera Martínez, Iztok Peterin, Ismael G. Yero. Roman domination in direct product graphs and rooted product graphs[J]. AIMS Mathematics, 2021, 6(10): 11084-11096. doi: 10.3934/math.2021643

Related Papers:

Abstract

Let $ G $ be a graph with vertex set $ V(G) $. A function $ f:V(G)\rightarrow \{0, 1, 2\} $ is a Roman dominating function on $ G $ if every vertex $ v\in V(G) $ for which $ f(v) = 0 $ is adjacent to at least one vertex $ u\in V(G) $ such that $ f(u) = 2 $. The Roman domination number of $ G $ is the minimum weight $ \omega(f) = \sum_{x\in V(G)}f(x) $ among all Roman dominating functions $ f $ on $ G $. In this article we study the Roman domination number of direct product graphs and rooted product graphs. Specifically, we give several tight lower and upper bounds for the Roman domination number of direct product graphs involving some parameters of the factors, which include the domination, (total) Roman domination, and packing numbers among others. On the other hand, we prove that the Roman domination number of rooted product graphs can attain only three possible values, which depend on the order, the domination number, and the Roman domination number of the factors in the product. In addition, theoretical characterizations of the classes of rooted product graphs achieving each of these three possible values are given.

References

[1]	T. Haynes, S. T. Hedetniemi, P. Slater, Domination in Graphs: Volume 2: Advanced Topics, Chapman & Hall/CRC Pure and Applied Mathematics, Taylor & Francis, 1998.
[2]	T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of Domination in Graphs, Chapman and Hall/CRC Pure and Applied Mathematics Series, Marcel Dekker, Inc. New York, 1998.
[3]	E. J. Cockayne, P. A. Jr. Dreyer, S. M. Hedetniemi, S. T. Hedetniemi, Roman domination in graphs, Discret. Math., 278 (2004), 11-22.
[4]	I. Stewart, Defend the Roman Empire!, Sci. Am., 281 (1999), 136-138.
[5]	E. W. Chambers, B. Kinnersley, N. Prince, D. B. West, Extremal problems for Roman domination, SIAM J. Discrete Math., 23 (2009), 1575-1586. doi: 10.1137/070699688
[6]	O. Favaron, H. Karami, R. Khoeilar, S. M. Sheikholeslami, On the Roman domination number of a graph, Discrete Math., 309 (2009), 3447-3451. doi: 10.1016/j.disc.2008.09.043
[7]	C. H. Liu, G. J. Chang, Upper bounds on Roman domination numbers of graphs, Discrete Math., 312 (2012), 1386-1391. doi: 10.1016/j.disc.2011.12.021
[8]	E. Zhu, Z. Shao, Extremal problems on weak Roman domination number, Inf. Process. Lett., 138 (2018), 12-18. doi: 10.1016/j.ipl.2018.05.009
[9]	A. Cabrera Martínez, C. García-Gómez, J. A. Rodríguez-Velázquez, Perfect domination, Roman domination and perfect Roman domination in lexicographic product graphs, Manuscript, (2020).
[10]	T. Kraner Šumenjak, P. Pavlič, A. Tepeh, On the Roman domination in the lexicographic product of graphs, Discrete Appl. Math., 160 (2012), 2030-2036. doi: 10.1016/j.dam.2012.04.008
[11]	I. G. Yero, On Clark & Suen bound type results for $k$-domination and Roman domination of Cartesian product graphs, Int. J. Comput. Math., 90 (2013), 522-526. doi: 10.1080/00207160.2012.742513
[12]	I. G. Yero, J. A. Rodríguez-Velázquez, Roman domination in Cartesian product graphs and strong product graphs, Appl. Anal. Discr. Math., 7 (2013), 262-274. doi: 10.2298/AADM130813017G
[13]	A. Klobučar, I. Puljić, Some results for Roman domination number on cardinal product of paths and cycles, Kragujev. J. Math., 38 (2014), 83-94. doi: 10.5937/KgJMath1401083K
[14]	A. Klobučar, I. Puljić, Roman domination number on cardinal product of paths and cycles, Croat. Oper. Res. Rev., 6 (2015), 71-78. doi: 10.17535/crorr.2015.0006
[15]	D. Kuziak, M. Lemańska, I. G. Yero, Domination-related parameters in rooted product graphs, Bull. Malays. Math. Sci. Soc., 39 (2019), 199-217.
[16]	I. G. Yero, D. Kuziak, A. Rondón Aguilar, Coloring, location and domination of corona graphs, Aequationes Math., 86 (2013), 1-21. doi: 10.1007/s00010-013-0207-9
[17]	T. W. Haynes, S. T. Hedetniemi, M. A. Henning (Eds.), Topics in Domination in Graphs, Developments in Mathematics, Springer International Publishing AG, 2020.
[18]	T. W. Haynes, S. T. Hedetniemi, M. A. Henning (Eds.), Structures of Domination in Graphs, Developments in Mathematics, Springer International Publishing AG, 2020.
[19]	M. A. Henning, A. Yeo, Total domination in graphs, New York, Springer, 2013.
[20]	P. M. Weichsel, The Kronecker product of graphs, Proc. Amer. Math. Soc., 13 (1962), 47-52. doi: 10.1090/S0002-9939-1962-0133816-6
[21]	R. Hamack, W. Imrich, S. Klavžar, Handbook of Product Graphs, Second Edition, CRC Press, Boca Raton, FL, 2011.
[22]	H. Abdollahzadeh Ahangar, M. A. Henning, V. Samodivkin, I. G. Yero, Total Roman domination in graphs, Appl. Anal. Discrete Math., 10 (2016), 501-517. doi: 10.2298/AADM160802017A
[23]	M. Chellali, T. Haynes, S. T. Hedetniemi, Roman and total domination, Quaest. Math., 38 (2015), 749-757.
[24]	A. Cabrera Martínez, D. Kuziak, I. Peterin, I. G. Yero, Dominating the direct product of two graphs through total Roman strategies, Mathematics, 8 (2020), 1438. doi: 10.3390/math8101793
[25]	D. F. Rall, Total domination in categorical products of graphs, Discuss. Math. Graph Theory, 25 (2005), 35-44. doi: 10.7151/dmgt.1257
[26]	C. D. Godsil, B. D. McKay, A new graph product and its spectrum, B. Aust. Math. Soc., 18 (1978), 21-28. doi: 10.1017/S0004972700007760
[27]	L. Barriere, F. Comellas, C. Dalfó, M. A. Fiol, The hierarchical product of graphs, Discrete App. Math., 157 (2009), 36-48. doi: 10.1016/j.dam.2008.04.018

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)