Article
Full entry |
PDF
(4.1 MB)
Feedback
PDF
(4.1 MB)
Feedback
Keywords:
domination; $k$-tuple total domination; probabilistic method
domination; $k$-tuple total domination; probabilistic method
Summary:
For a fixed positive integer $k$ and $G=(V, E)$ a connected graph of order $n$, whose minimum vertex degree is at least $k$, a set $S\subseteq V$ is a total $k$-dominating set, also known as a $k$-tuple total dominating set, if every vertex $v\in V$ has at least $k$ neighbors in $S$. The minimum size of a total $k$-dominating set for $G$ is called the total $k$-domination number of $G$, denoted by $\gamma_{kt}(G)$. The total $k$-domination problem is to determine a minimum total $k$-dominating set of $G$. Since the exact problem is in general quite difficult to solve, it is also of interest to have good upper bounds on the total $k$-domination number. In this paper, we present a probabilistic approach to computing an upper bound for the total $k$-domination number that improves on some previous results.
References:
[1] Alipour, S., Jafari, A.: Upper bounds for the domination numbers of graphs using Turán's theorem and Lovasz local lemma. Graphs Combin. 35 (2019), 1153-1160. DOI | MR 4003664
[2] Alon, N., Spencer, J H.: The Probabilistic Method. Wiley, New York 2016. MR 3524748
[3] Bartle, R. G.: The Elements of Real Analysis. Wiley, New York 1991. MR 0393369
[4] Cockayne, E J., Dawes, R. M., Hedetniemi, S. T.: Total domination in graphs. Networks 10 (1980),3, 211-219. DOI | MR 0584887
[5] Haynes, T. W., Hedetniemi, S., Slater, P.: Fundamentals of Domination in Graphs. Marcel Dekker, New York 1998. MR 1605684
[6] Henning, M. A., Kazemi, A. P.: $k$-tuple total domination in graphs. Discrete Appl. Math. 158 (2010), 9, 1006-1011. DOI | MR 2607047
[7] Henning, M. A., Yeo, A.: Strong transversals in hypergraphs and double total domination in graphs. SIAM J. Discrete Math. 24 (2010), 4, 1336-1355. DOI | MR 2735927
[8] Henning, M. A., Yeo, A.: Total Domination in Graphs. Springer, New York 2013. DOI | MR 3060714
[9] Malarvizhi, J., Divya, G.: Domination and edge domination in single valued neutrosophic graph. Adv. Appl. Math. Sci. 20 (2021), 5, 721-732.
[10] Pradhan, D.: Algorithmic aspects of $k$-tuple total domination in graphs. Inform. Process. Lett. 112 (2012), 21, 816-822. DOI | MR 2960327
[11] Yuede, M., Qingqiong, C., Shunyu, Y.: Integer linear programming models for the weighted total domination problem. Appl. Math. Comput. 358 (2019), 146-150. DOI | MR 3942198
Search
Partner of
