Double total domination number of Cartesian product of paths

Linyu Li; Jun Yue; Xia Zhang; Linyu Li; Jun Yue; Xia Zhang

doi:10.3934/math.2023479

AIMS Mathematics

2023, Volume 8, Issue 4: 9506-9519. doi: 10.3934/math.2023479

Previous Article Next Article

Research article

Double total domination number of Cartesian product of paths

Linyu Li ¹,
Jun Yue ²,
Xia Zhang ^{1
,
,}

1.
School of Mathematics and Statistics, Shandong Normal University, Jinan 250358, China
2.
School of Mathematics Science, Tiangong University, Tianjin 300387, China

Received: 10 December 2022 Revised: 03 February 2023 Accepted: 08 February 2023 Published: 20 February 2023
MSC : 05C69

A vertex set $ S $ of a graph $ G $ is called a double total dominating set if every vertex in $ G $ has at least two adjacent vertices in $ S $. The double total domination number $ \gamma_{\times 2, t}(G) $ of $ G $ is the minimum cardinality over all the double total dominating sets in $ G $. Let $ G \square H $ denote the Cartesian product of graphs $ G $ and $ H $. In this paper, the double total domination number of Cartesian product of paths is discussed. We determine the values of $ \gamma_{\times 2, t}(P_i\square P_n) $ for $ i = 2, 3 $, and give lower and upper bounds of $ \gamma_{\times 2, t}(P_i\square P_n) $ for $ i \geq 4 $.
- dominating sets,
- total domination,
- double total domination,
- Cartesian product,
- paths
Citation: Linyu Li, Jun Yue, Xia Zhang. Double total domination number of Cartesian product of paths[J]. AIMS Mathematics, 2023, 8(4): 9506-9519. doi: 10.3934/math.2023479

Related Papers:

Abstract

A vertex set $ S $ of a graph $ G $ is called a double total dominating set if every vertex in $ G $ has at least two adjacent vertices in $ S $. The double total domination number $ \gamma_{\times 2, t}(G) $ of $ G $ is the minimum cardinality over all the double total dominating sets in $ G $. Let $ G \square H $ denote the Cartesian product of graphs $ G $ and $ H $. In this paper, the double total domination number of Cartesian product of paths is discussed. We determine the values of $ \gamma_{\times 2, t}(P_i\square P_n) $ for $ i = 2, 3 $, and give lower and upper bounds of $ \gamma_{\times 2, t}(P_i\square P_n) $ for $ i \geq 4 $.

References

[1]	S. Bermudo, J. C. Hernández-Gómez, J. M. Sigarreta, Total $k$-dominaiton in strong product graphs, Discrete Appl. Math., 263 (2019), 51–58. https://doi.org/10.1016/J.DAM.2018.03.043 doi: 10.1016/J.DAM.2018.03.043
[2]	S. Bermudo, D. L. Jalemskaya, J. M. Sigarreta, Total 2-domination in grid graphs, Utilitas Math., 110 (2019), 151–173.
[3]	S. Bermudo, J. L. Sanchéz, J. M. Sigarreta, Total $k$-domination number in Cartesian product graphs, Period. Math. Hung., 75 (2017), 255–267. https://doi.org/10.1007/s10998-017-0191-2 doi: 10.1007/s10998-017-0191-2
[4]	J. A. Bondy, U. S. R. Murty, Graph theory, Graduate Texts in Mathematics, Vol. 244, London: Springer-Verlag, 2008.
[5]	A. Cabrera-Martínez, F. A. Hernández-Mira, New bounds on the double total domination number of graphs, Bull. Malays. Math. Sci. Soc., 45 (2021), 443–453. https://doi.org/10.1007/s40840-021-01200-0 doi: 10.1007/s40840-021-01200-0
[6]	N. Campanelli, D. Kuziak, Total Roman domination in the lexicographic product of graphs, Discrete Appl. Math., 263 (2019), 88–95. https://doi.org/10.1016/J.DAM.2018.06.008 doi: 10.1016/J.DAM.2018.06.008
[7]	W. Carballosa, J. Wisby, Total $k$-domination in Cartesian product of complete graphs, arXiv, 2020. https://doi.org/10.48550/arXiv.2001.07850
[8]	E. J. Cockayne, R. M. Dawes, S. T. Hedetniemi, Total domination in graphs, Networks, 10 (1980), 211–219. https://doi.org/10.1002/net.3230100304 doi: 10.1002/net.3230100304
[9]	M. A. Henning, A survey of selected recent results on total domination in graphs, Discrete Math., 309 (2009), 32–63. https://doi.org/10.1016/j.disc.2007.12.044 doi: 10.1016/j.disc.2007.12.044
[10]	M. A. Henning, A. P. Kazemi, $k$-tuple total domination in graphs, Discrete Appl. Math., 158 (2010), 1006–1011. https://doi.org/10.1016/j.dam.2010.01.009 doi: 10.1016/j.dam.2010.01.009
[11]	M. A. Henning, A. P. Kazemi, $k$-tuple total domination in cross products of graphs, J. Comb. Optim., 24 (2012), 339–346. https://doi.org/10.1007/s10878-011-9389-z doi: 10.1007/s10878-011-9389-z
[12]	M. A. Henning, A. Yeo, Total domination in graphs, Springer Monographs in Mathematics, New York: Springer, 2013. https://doi.org/10.1007/978-1-4614-6525-6
[13]	F. Hu, M. Y. Sohn, X. Chen, Total and paired domination numbers of $C_m$ bundles over a cycle $C_n$, J. Comb. Optim., 32 (2016), 608–625. https://doi.org/10.1007/s10878-015-9885-7 doi: 10.1007/s10878-015-9885-7
[14]	F. Hu, J. Xu, Total and paired domination numbers of toroidal meshes, J. Comb. Optim., 27 (2014), 369–378. https://doi.org/10.1007/s10878-012-9519-2 doi: 10.1007/s10878-012-9519-2
[15]	A. P. Kazemi, B. Pahlavsay, R. J. Stones, Cartesian product graphs and $k$-tuple total domination, Filomat, 32 (2018), 6713–6731. https://doi.org/10.2298/FIL1819713K doi: 10.2298/FIL1819713K
[16]	N. Li, X. Hou, On the total $k$-domination number of Cartesian products of graphs, J. Comb. Optim., 18 (2009), 173–178. https://doi.org/10.1007/s10878-008-9144-2 doi: 10.1007/s10878-008-9144-2
[17]	N. J. Rad, Upper bounds on the $k$-tuple domination number and $k$-tuple total domination number of a graph, Australas. J. Comb., 73 (2019), 280–290.
[18]	J. Yue, S. Zhang, Y. Zhu, S. Klavžar, Y. Shi, The annihilation number does not bound the 2-domination number from the above, Discrete Math., 343 (2019), 111707. https://doi.org/10.1016/j.disc.2019.111707 doi: 10.1016/j.disc.2019.111707
[19]	J. Yue, Y. Zhu, M. Wei, The annihilation number and the total domination number of a tree-like graph, Appl. Math. Comput., 380 (2020), 125240. https://doi.org/10.1016/j.amc.2020.125240 doi: 10.1016/j.amc.2020.125240

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)