Research article

Roman domination in direct product graphs and rooted product graphs

  • 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.

    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:

  • 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.



    加载中


    [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
  • © 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)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(1550) PDF downloads(100) Cited by(1)

Article outline

Figures and Tables

Figures(1)

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog