Article in volume
Authors:
Title:
Total protection of lexicographic product graphs
PDFSource:
Discussiones Mathematicae Graph Theory 42(3) (2022) 967-984
Received: 2019-06-13 , Revised: 2020-03-25 , Accepted: 2020-03-26 , Available online: 2020-04-21 , https://doi.org/10.7151/dmgt.2318
Abstract:
Given a graph $G$ with vertex set $V(G)$, a function $f : V(G) \rightarrow
\{0,1,2 \}$ is said to be a total dominating function if $\sum_{u\in N(v)}f(u)>0$
for every $v\in V(G)$, where $N(v)$ denotes the open neighbourhood of $v$.
Let $V_i=\{x\in V(G):f(x)=i\}$. A total dominating function $f$ is a total
weak Roman dominating function if for every vertex $v\in V_0$ there exists a
vertex $u\in N(v)\cap (V_1\cup V_2)$ such that the function $f'$, defined by
$f'(v)=1$, $f'(u)=f(u)-1$ and $f'(x)=f(x)$ whenever $x\in V(G)\setminus\{u,v\}$,
is a total dominating function as well. If $f$ is a total weak Roman dominating
function and $V_2=\emptyset$, then we say that $f$ is a secure total dominating
function. The weight of a function $f$ is defined to be $\omega(f)=
\sum_{v\in 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
References:
- 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 - S. Benecke, E.J. Cockayne and C.M. Mynhardt, Secure total domination in graphs, Util. Math. 74 (2007) 247–259.
- S. Benecke, E.J. Cockayne and C.M. Mynhardt, Total protection of a graph, unpublished manuscript.
- R. Brigham, J. Carrington and R. Vitray, Connected graphs with maximum total domination number, J. Combin. Math. Combin. Comput. 34 (2000) 81–96.
- 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 - 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 - 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 - 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 - 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 - 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 - 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.
- 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.
- 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 - 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 - T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Taylor & Francis, 1998).
- T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).
- 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 - 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 - M.A. Henning and A. Yeo, Total Domination in Graphs (Springer, New York, 2013).
https://doi.org/10.1007/978-1-4614-6525-6 - 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 - 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 - 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 - I. Stewart, Defend the Roman Empire$ !$, Sci. Amer. 281 (1999) 136–138.
https://doi.org/10.1038/scientificamerican1299-136
Close