Perfect Domination, Roman Domination and Perfect Roman Domination in Lexicographic Product Graphs.

• Autorzy: Cabrera Martínez Abel , García-Gómez César , Rodríguez-Velázquez Juan Alberto

Identyfikatory

DOI

10.3233/FI-222108

• Języki publikacji: EN

Abstrakty

EN

The aim of this paper is to obtain closed formulas for the perfect domination number, the Roman domination number and the perfect Roman domination number of lexicographic product graphs. We show that these formulas can be obtained relatively easily for the case of the first two parameters. The picture is quite different when it concerns the perfect Roman domination number. In this case, we obtain general bounds and then we give sufficient and/or necessary conditions for the bounds to be achieved. We also discuss the case of perfect Roman graphs and we characterize the lexicographic product graphs where the perfect Roman domination number equals the Roman domination number.

Słowa kluczowe

EN

lexicographic product; perfect domination; perfect Roman domination; Roman domination

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 185, nr 3
• Strony: 201--220
• Opis fizyczny: Bibliogr. 34 poz., rys.

Twórcy

autor

Cabrera Martínez Abel

• Universitat Rovira i Virgili, Departament d'Enginyeria Informàtica i Matemàtiques, Av. Països Catalans 26, 43007 Tarragona, Spain

autor

García-Gómez César

• Universitat Rovira i Virgili, Departament d'Enginyeria Informàtica i Matemàtiques, Av. Països Catalans 26, 43007 Tarragona, Spain

autor

Rodríguez-Velázquez Juan Alberto

• Universitat Rovira i Virgili, Departament d'Enginyeria Informàtica i Matemàtiques, Av. Països Catalans 26, 43007 Tarragona, Spain

Bibliografia

• [1] Abdollahzadeh Ahangar H, Henning MA, Samodivkin V, Yero IG. Total Roman domination in graphs, Appl. Anal. Discrete Math. 2016. 10(2):501-517.
• [2] Arriola BH, Canoy SR, Jr. Doubly connected domination in the corona and lexicographic product of graphs, Appl. Math. Sci. (Ruse) 2014. 8(29-32):1521-1533. doi:10.12988/ams.2014.4136
• [3] Banerjee S, Keil JM, Pradhan D. Perfect Roman domination in graphs, Theoret. Comput. Sci. 2019. 7(10)797. doi:10.3390/math7100997.
• [4] Cabrera Martínez A, Cabrera García S, Rodríguez-Velázquez JA. Double domination in lexicographic product graphs, Discrete Appl. Math. 2020. 284:290-300. doi:10.1016/j.dam.2020.03.045.
• [5] Cabrera Martínez A, Estrada-Moreno A, Rodríguez-Velázquez JA. From Italian domination in lexicographic product graphs to w-domination in graphs. Ars Math. Contemp. 2022. 22(1)P1.04.doi:10.26493/1855-3974.2318.fb9.
• [6] Cabrera Martínez A, Rodríguez-Velázquez JA. Closed formulas for the total Roman domination number of lexicographic product graphs. Ars Math. Contemp. 2021. 20(2):233-241. doi:10.26493/1855-3974.2284.aeb.
• [7] Cabrera Martínez A, Rodríguez-Velázquez JA. Total protection of lexicographic product graphs, Discuss. Math. Graph Theory. In press. doi:10.7151/dmgt.2318
• [8] Campanelli N, Kuziak D. Total Roman domination in the lexicographic product of graphs, Discrete Appl. Math. 2019. 263:88-95. doi:10.1016/j.dam.2018.06.008.
• [9] Clark L. Perfect domination in random graphs, J. Combin. Math. Combin. Comput. 1993. 14:173-182.
• [10] Cockayne EJ, Dreyer Jr. PA, Hedetniemi SM, Hedetniemi ST. Roman domination in graphs, Discrete Math. 2004. 278(1-3):11-22. doi:10.1016/j.disc.2003.06.004.
• [11] Cockayne EJ, Hartnell BL, Hedetniemi ST, Laskar R. Perfect domination in graphs, J. Comb. Inf. Syst. Sci 1993. 18:136-148.
• [12] Darkooti M, Alhevaz A, Rahimi S, Rahbani H. On perfect Roman domination number in trees: complexity and bounds, J. Comb. Optim. 2019. 38(3):712-720. doi:10.1007/s10878-019-00408-y.
• [13] Dejter IJ. Perfect domination in regular grid graphs, Australas. J. Combin. 2008. 42:99-114.
• [14] Dettlaff M, Lemańska M, Rodríguez-Velázquez JA, Zuazua R. On the super domination number of lexicographic product graphs, Discrete Appl. Math. 2019. 263:118-129. doi:10.1016/j.dam.2018.03.082.
• [15] Fellows MR, Hoover MN. Perfect domination, Australas. J. Combin. 1991. 3:141-150. ID:29796780.
• [16] Hammack R, Imrich W, Klavžar S. Handbook of product graphs, Discrete Mathematics and its Applications, 2nd ed., CRC Press, 2011. ISBN-10:1439813043, 13:978-1439813041.
• [17] Haynes T, Hedetniemi S, Slater P. Domination in Graphs: Volume 2: Advanced Topics, Chapman& Hall/CRC Pure and Applied Mathematics, Taylor & Francis, 1998. ISBN-10:0824700341, 13:978-0824700348.
• [18] Haynes TW, Hedetniemi ST, Slater PJ. Fundamentals of Domination in Graphs, Chapman and Hall/CRC Pure and Applied Mathematics Series, Marcel Dekker, Inc. New York, 1998. ISBN-10:0824700333, 13:978-0824700331.
• [19] Henning MA, Klostermeyer WF. Perfect Roman domination in regular graphs, Appl. Anal. Discrete Math. 2018. 12(1):143-152. doi:10.2298/AADM1801143H.
• [20] Henning MA, Klostermeyer WF, MacGillivray G. Perfect Roman domination in trees, Discrete Appl. Math. 2018. 236:235-245. doi:10.1016/j.dam.2017.10.027.
• [21] Imrich W, Klavžar S. Product graphs, structure and recognition, Wiley-Interscience series in discrete mathematics and optimization, Wiley, 2000. ISBN-10:0471370398, 13:978-0471370390.
• [22] Klostermeyer WF. A taxonomy of perfect domination, J. Discrete Math. Sci. Cryptogr. 2015. 18(1-2):105-116. doi:10.1080/09720529.2014.914288.
• [23] Kuziak D, Peterin I, Yero IG. Efficient open domination in graph products, Discrete Math. Theor. Comput. Sci. 2014. 16(1):105-120. doi:10.46298/dmtcs.1267.
• [24] Kwon YS, Lee J. Perfect domination sets in Cayley graphs, Discrete Appl. Math. 2014. 162:259-263. doi:10.1016/j.dam.2013.09.020.
• [25] Liu J, Zhang X, Meng J. Domination in lexicographic product digraphs, Ars Combin. 2015. 120:23-32.
• [26] Livingston M, Stout QF. Perfect dominating sets, Congr. Numer. 1990. 79:187-203.
• [27] Meir A, Moon JW. Relations between packing and covering numbers of a tree, Pacific J. Math. 1975. 61(1):225-233.
• [28] Nowakowski RJ, Rall DF. Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory 1996. 16(1):53-79. doi:10.7151/dmgt.1023.
• [29] Sheikholeslami SM, Chellali M, Soroudi M. A characterization of perfect Roman trees, Discrete Appl. Math. 2020. 285:501-508. doi:10.1016/j.dam.2020.06.014.
• [30] Šumenjak TK, Pavliˇc P, Tepeh A. On the Roman domination in the lexicographic product of graphs, Discrete Appl. Math. 2012. 160(13-14):2030-2036. doi:10.1016/j.dam.2012.04.008.
• [31] Šumenjak TK, Rall DF, Tepeh A. Rainbow domination in the lexicographic product of graphs, Discrete Appl. Math. 2013. 161(13-14):2133-2141. doi:10.1016/j.dam.2013.03.011.
• [32] Valveny M, Pérez-Rosés H, Rodríguez-Velázquez JA. On the weak Roman domination number of lexicographic product graphs, Discrete Appl. Math. 2019. 263:257-270.
• [33] Yue J, Song J. Note on the perfect Roman domination number of graphs, Appl. Math. Comput. 2020. 364:124685. doi:10.1016/j.amc.2019.124685.
• [34] Zhang X, Liu J, Meng J. Domination in lexicographic product graphs, Ars Combin. 2011. 101:251-256.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)