Geodesic
Protection of Lexicographic Product Graphs
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 1, pp. 139-158.

Voir la notice de l'article provenant de la source Library of Science

In this paper, we study the weak Roman domination number and the secure domination number of lexicographic product graphs. In particular, we show that these two parameters coincide for almost all lexicographic product graphs. Furthermore, we obtain tight bounds and closed formulas for these parameters.
Keywords: lexicographic product, weak Roman domination, secure domination, total domination, double total domination 
@article{DMGT_2022_42_1_a9,
     author = {Klein, Douglas J. and Rodr{\'\i}guez-Vel\'azquez, Juan A.},
     title = {Protection of {Lexicographic} {Product} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {139--158},
     publisher = {mathdoc},
     volume = {42},
     number = {1},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a9/}
}
TY  - JOUR
AU  - Klein, Douglas J.
AU  - Rodríguez-Velázquez, Juan A.
TI  - Protection of Lexicographic Product Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 139
EP  - 158
VL  - 42
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a9/
LA  - en
ID  - DMGT_2022_42_1_a9
ER  - 
%0 Journal Article
%A Klein, Douglas J.
%A Rodríguez-Velázquez, Juan A.
%T Protection of Lexicographic Product Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 139-158
%V 42
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a9/
%G en
%F DMGT_2022_42_1_a9
Klein, Douglas J.; Rodríguez-Velázquez, Juan A. Protection of Lexicographic Product Graphs. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 1, pp. 139-158. http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a9/

[1] B.H. Arriola and S.R. Canoy, Jr., Doubly connected domination in the corona and lexicographic product of graphs, Appl. Math. Sci. 8 (2014) 1521–1533. https://doi.org/10.12988/ams.2014.4136

[2] B. Bollobás and E.J. Cockayne, Graph-theoretic parameters concerning domination, independence, and irredundance, J. Graph Theory 3 (1979) 241–249. https://doi.org/10.1002/jgt.3190030306

[3] H. Boumediene Merouane and M. Chellali, On secure domination in graphs, Inform. Process. Lett. 115 (2015) 786–790. https://doi.org/10.1016/j.ipl.2015.05.006

[4] A.P. Burger, M.A. Henning and J.H. van Vuuren, Vertex covers and secure domination in graphs, Quaest. Math. 31 (2008) 163–171. https://doi.org/10.2989/QM.2008.31.2.5.477

[5] A. Cabrera Martínez, L.P. Montejano and J.A. Rodríguez-Velázquez, Total weak Roman domination in graphs, Symmetry 11 (6) (2019) #831. https://doi.org/10.3390/sym11060831

[6] M. Chellali, T.W. Haynes and S.T. Hedetniemi, Bounds on weak Roman and 2- rainbow domination numbers, Discrete Appl. Math. 178 (2014) 27–32. https://doi.org/10.1016/j.dam.2014.06.016

[7] E.J. Cockayne, R.M. Dawes and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211–219. https://doi.org/10.1002/net.3230100304

[8] E.J. Cockayne, O. Favaron and C.M. Mynhardt, Secure domination, weak Roman domination and forbidden subgraphs, Bull. Inst. Combin. Appl. 39 (2003) 87–100.

[9] E.J. Cockayne, P.J.P. Grobler, W.R. Gründlingh, J. Munganga and J.H. van Vuuren, Protection of a graph, Util. Math. 67 (2005) 19–32.

[10] E.J. Cockayne, P.A. Dreyer Jr., S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11–22. https://doi.org/10.1016/j.disc.2003.06.004

[11] M. Dettla, M. Lemańska, J.A. Rodríguez-Velázquez and R. Zuazua, On the super domination number of lexicographic product graphs, Discrete Appl. Math. 263 (2019) 118–129. https://doi.org/10.1016/j.dam.2018.03.082

[12] W. Goddard and M.A. Henning, Domination in planar graphs with small diameter, J. Graph Theory 40 (2002) 1–25. https://doi.org/10.1002/jgt.10027

[13] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs (CRC Press, 2011). https://doi.org/10.1201/b10959

[14] T. Haynes, S. Hedetniemi and P. Slater, Domination in Graphs: Volume 2: Advanced Topics (CRC Press, New York, 1998).

[15] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (CRC Press, New York, 1998).

[16] M.A. Henning and S.T. Hedetniemi, Defending the Roman Empire—A new strategy, Discrete Math. 266 (2003) 239–251. https://doi.org/10.1016/S0012-365X(02)00811-7

[17] M.A. Henning and A. Yeo, Total Domination in Graphs (Springer, New York, 2013). https://doi.org/10.1007/978-1-4614-6525-6

[18] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (Wiley-Interscience, New York, 2000).

[19] W.F. Klostermeyer and C.M. Mynhardt, Secure domination and secure total domination in graphs, Discuss. Math. Graph Theory 28 (2008) 267–284. https://doi.org/10.7151/dmgt.1405

[20] J. Liu, X. Zhang and J. Meng, Domination in lexicographic product digraphs, Ars Combin. 120 (2015) 23–32.

[21] R.J. Nowakowski and D.F. Rall, Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory 16 (1996) 53–79. https://doi.org/10.7151/dmgt.1023

[22] I. Stewart, Defend the Roman Empire !, Sci. Amer. 281 (1999) 136–138. https://doi.org/10.1038/scientificamerican1299-136

[23] T.K. Šumenjak, P. Pavlič and A. Tepeh, On the Roman domination in the lexicographic product of graphs, Discrete Appl. Math. 160 (2012) 2030–2036. https://doi.org/10.1016/j.dam.2012.04.008

[24] T.K. Šumenjak, D.F. Rall and A. Tepeh, Rainbow domination in the lexicographic product of graphs, Discrete Appl. Math. 161 (2013) 2133–2141. https://doi.org/10.1016/j.dam.2013.03.011

[25] M. Valveny, H. Pérez-Rosés and J.A. Rodríguez-Velázquez, On the weak Roman domination number of lexicographic product graphs, Discrete Appl. Math. 263 (2019) 257–270. https://doi.org/10.1016/j.dam.2018.03.039

[26] M. Valveny and J.A. Rodríguez-Velázquez, Protection of graphs with emphasis on Cartesian product graphs, Filomat 33 (2019) 319–333. https://doi.org/10.2298/FIL1901319V