DMGT

Let $G$ be a graph with no isolated vertex. A function $f: V(G)\rightarrow \{0,1,2\}$ is a total $\{2\}$-dominating function on $G$ if $\sum_{u\in N_G(v)}f(u)\geq 2$ for every vertex $v\in V(G)$. The total $\{2\}$-domination number of $G$ is the minimum weight $\omega(f)= \sum_{v\in V(G)}f(v)$ among all total $\{2\}$-dominating functions $f$ on $G$. In this paper, we study some relationships among some parameters of a graph and the total $\{2\}$-domination number of its complement, emphasizing in results of the Nordhaus-Gaddum type.

Keywords:

total $\{2\}$-domination number, total domination number, complement, Nordhaus-Gaddum bounds

References:

M. Aouchiche and P. Hansen, A survey of Nordhaus-Gaddum type relations, Discrete Appl. Math. 161 (2013) 466–546.
https://doi.org/10.1016/j.dam.2011.12.018
F. Bonomo, B. Brešar, L.N. Grippo, M. Milanič and M.D. Safe, Domination parameters with number $2$: Interrelations and algorithmic consequences, Discrete Appl. Math. 235 (2018) 23–50.
https://doi.org/10.1016/j.dam.2017.08.017
A. Cabrera Martínez, A. Estrada-Moreno and J.A. Rodríguez-Velázquez, From Italian domination in lexicographic product graphs to $w$-domination in graphs, Ars Math. Contemp. 22 (2022) P1.04.
https://doi.org/10.26493/1855-3974.2318.fb9
A. Cabrera-Martínez, L.P. Montejano and J.A. Rodríguez-Velázquez, From {$w$}-domination in graphs to domination parameters in lexicographic product graphs, Bull. Malays. Math. Sci. Soc. 46 (2023) 109.
https://doi.org/10.1007/s40840-023-01502-5
A. Cabrera-Martínez, I. Rios Villamar, J.M. Rueda-Vázquez and J.M. Sigarreta, Double total domination in the generalized lexicographic product of graphs, Quaest. Math. 47 (2024) 689–703.
https://doi.org/10.2989/16073606.2023.2252183
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
W.J. Desormeaux, T.W. Haynes, M.A. Henning and A. Yeo, Total domination in graphs with diameter $2$, J. Graph Theory 75 (2013) 91–103.
https://doi.org/10.1002/jgt.21725
O. Favaron, H. Karami and S.M. Sheikholeslami, Total domination and total domination subdivision number of a graph and its complement, Discrete Math. 308 (2008) 4018–4023.
https://doi.org/10.1016/j.disc.2007.07.088
T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Topics in Domination in Graphs, Dev. Math. 64 (Springer, Cham, 2020).
https://doi.org/10.1007/978-3-030-51117-3
M.A. Henning, A. Yeo, Total Domination in Graphs, Springer Monogr. Math. (Springer, New York, 2013).
https://doi.org/10.1007/978-1-4614-6525-6
R. Khoeilar, H. Karami, M. Chellali, S.M. Sheikholeslami and L. Volkmann, Nordhaus-Gaddum type results for connected and total domination, RAIRO Oper. Res. 55 (2021) S853–S862.
https://doi.org/10.1051/ro/2020025
I. Ríos Villamar, A. Cabrera-Martínez, J.L. Sánchez and J.M. Sigarreta, Relating the total $\{2\}$-domination number with the total domination number of graphs, Discrete Appl. Math. 333 (2023) 90–95.
https://doi.org/10.1016/j.dam.2023.03.018