| Title:
|
On upper bounds for total $k$-domination number via the probabilistic method (English) |
| Author:
|
Sigarreta, Saylí |
| Author:
|
Sigarreta, Saylé |
| Author:
|
Cruz-Suárez, Hugo |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
59 |
| Issue:
|
4 |
| Year:
|
2023 |
| Pages:
|
537-547 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
domination |
| Keyword:
|
$k$-tuple total domination |
| Keyword:
|
probabilistic method |
| MSC:
|
05C30 |
| MSC:
|
05C65 |
| MSC:
|
05C69 |
| idZBL:
|
Zbl 07790649 |
| idMR:
|
MR4660377 |
| DOI:
|
10.14736/kyb-2023-4-0537 |
| . |
| Date available:
|
2023-10-17T07:54:50Z |
| Last updated:
|
2024-02-13 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/151850 |
| . |
| Reference:
|
[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. MR 4003664, |
| Reference:
|
[2] Alon, N., Spencer, J H.: The Probabilistic Method..Wiley, New York 2016. MR 3524748 |
| Reference:
|
[3] Bartle, R. G.: The Elements of Real Analysis..Wiley, New York 1991. MR 0393369 |
| Reference:
|
[4] Cockayne, E J., Dawes, R. M., Hedetniemi, S. T.: Total domination in graphs..Networks 10 (1980),3, 211-219. MR 0584887, |
| Reference:
|
[5] Haynes, T. W., Hedetniemi, S., Slater, P.: Fundamentals of Domination in Graphs..Marcel Dekker, New York 1998. MR 1605684 |
| Reference:
|
[6] Henning, M. A., Kazemi, A. P.: $k$-tuple total domination in graphs..Discrete Appl. Math. 158 (2010), 9, 1006-1011. MR 2607047, |
| Reference:
|
[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. MR 2735927, |
| Reference:
|
[8] Henning, M. A., Yeo, A.: Total Domination in Graphs..Springer, New York 2013. MR 3060714, |
| Reference:
|
[9] Malarvizhi, J., Divya, G.: Domination and edge domination in single valued neutrosophic graph..Adv. Appl. Math. Sci. 20 (2021), 5, 721-732. |
| Reference:
|
[10] Pradhan, D.: Algorithmic aspects of $k$-tuple total domination in graphs..Inform. Process. Lett. 112 (2012), 21, 816-822. MR 2960327, |
| Reference:
|
[11] Yuede, M., Qingqiong, C., Shunyu, Y.: Integer linear programming models for the weighted total domination problem..Appl. Math. Comput. 358 (2019), 146-150. MR 3942198, |
| . |
