Geodesic
Total Protection of Lexicographic Product Graphs
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 967-984.

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

Given a graph G with vertex set V (G), a function f : V (G) → 0, 1, 2 is said to be a total dominating function if Σu∈N(v) f(u) gt; 0 for every v ∈ V (G), where N(v) denotes the open neighbourhood of v. Let Vi = x ∈ V (G) : f(x) = i. A total dominating function f is a total weak Roman dominating function if for every vertex v ∈ V0 there exists a vertex u ∈ N(v) ∩ (V1 ∪ V2) such that the function f′, defined by f′(v) = 1, f′(u) = f(u) − 1 and f′(x) = f(x) whenever x ∈ V (G) u, v, is a total dominating function as well. If f is a total weak Roman dominating function and V2 = ∅, then we say that f is a secure total dominating function. The weight of a function f is defined to be ω(f) = Σv∈V (G) f(v). The total weak Roman domination number (secure total domination number) of a graph G is the minimum weight among all total weak Roman dominating functions (secure total dominating functions) on G. In this article, we show that these two parameters coincide for lexicographic product graphs. Furthermore, we obtain closed formulae and tight bounds for these parameters in terms of invariants of the factor graphs involved in the product.
Keywords: total weak Roman domination, secure total domination, total domination, lexicographic product 
@article{DMGT_2022_42_3_a17,
     author = {Mart{\'\i}nez, Abel Cabrera and Rodr{\'\i}guez-Vel\'azquez, Juan Alberto},
     title = {Total {Protection} of {Lexicographic} {Product} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {967--984},
     publisher = {mathdoc},
     volume = {42},
     number = {3},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a17/}
}
TY  - JOUR
AU  - Martínez, Abel Cabrera
AU  - Rodríguez-Velázquez, Juan Alberto
TI  - Total Protection of Lexicographic Product Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 967
EP  - 984
VL  - 42
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a17/
LA  - en
ID  - DMGT_2022_42_3_a17
ER  - 
%0 Journal Article
%A Martínez, Abel Cabrera
%A Rodríguez-Velázquez, Juan Alberto
%T Total Protection of Lexicographic Product Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 967-984
%V 42
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a17/
%G en
%F DMGT_2022_42_3_a17
Martínez, Abel Cabrera; Rodríguez-Velázquez, Juan Alberto. Total Protection of Lexicographic Product Graphs. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 967-984. http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a17/

[1] R.A. Beeler, T.W. Haynes and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016) 23–29. https://doi.org/10.1016/j.dam.2016.03.017

[2] S. Benecke, E.J. Cockayne and C.M. Mynhardt, Secure total domination in graphs, Util. Math. 74 (2007) 247–259.

[3] S. Benecke, E.J. Cockayne and C.M. Mynhardt, Total protection of a graph, unpublished manuscript.

[4] R. Brigham, J. Carrington and R. Vitray, Connected graphs with maximum total domination number, J. Combin. Math. Combin. Comput. 34 (2000) 81–96.

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

[6] A. Cabrera Martínez and J.A. Rodríguez-Velázquez, On the secure total domination number of graphs, Symmetry 11 (2019) No. 1165. https://doi.org/10.3390/sym11091165

[7] M. Chellali, T.W. Haynes, S.T. Hedetniemi and A. McRae, Roman {2} -domination, Discrete Appl. Math. 204 (2016) 22–28. https://doi.org/10.1016/j.dam.2015.11.013

[8] 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

[9] 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

[10] 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

[11] 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.

[12] 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.

[13] O. Duginov, Secure total domination in graphs: Bounds and complexity, Discrete Appl. Math. 222 (2017) 97–108. https://doi.org/10.1016/j.dam.2016.08.018

[14] T.W. Haynes and M.A. Henning, Perfect Italian domination in trees, Discrete Appl. Math. 260 (2019) 164–177. https://doi.org/10.1016/j.dam.2019.01.038

[15] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Taylor & Francis, 1998).

[16] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).

[17] M.A. Henning and W.F. Klostermeyer, Italian domination in trees, Discrete Appl. Math. 217 (2017) 557–564. https://doi.org/10.1016/j.dam.2016.09.035

[18] 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

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

[20] 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

[21] A. Meir and J.W. Moon, Relations between packing and covering numbers of a tree, Pacific J. Math. 61 (1975) 225–233. https://doi.org/10.2140/pjm.1975.61.225

[22] 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

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