Geodesic
On upper bounds for total $k$-domination number via the probabilistic method
Kybernetika, Tome 59 (2023) no. 4, pp. 537-547
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.14736/kyb-2023-4-0537
Classification : 05C30, 05C65, 05C69
Keywords: domination; $k$-tuple total domination; probabilistic method 
@article{10_14736_kyb_2023_4_0537,
     author = {Sigarreta, Sayl{\'\i} and Sigarreta, Sayl\'e and Cruz-Su\'arez, Hugo},
     title = {On upper bounds for total $k$-domination number via the probabilistic method},
     journal = {Kybernetika},
     pages = {537--547},
     year = {2023},
     volume = {59},
     number = {4},
     doi = {10.14736/kyb-2023-4-0537},
     mrnumber = {4660377},
     zbl = {07790649},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2023-4-0537/}
}
TY  - JOUR
AU  - Sigarreta, Saylí
AU  - Sigarreta, Saylé
AU  - Cruz-Suárez, Hugo
TI  - On upper bounds for total $k$-domination number via the probabilistic method
JO  - Kybernetika
PY  - 2023
SP  - 537
EP  - 547
VL  - 59
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2023-4-0537/
DO  - 10.14736/kyb-2023-4-0537
LA  - en
ID  - 10_14736_kyb_2023_4_0537
ER  - 
%0 Journal Article
%A Sigarreta, Saylí
%A Sigarreta, Saylé
%A Cruz-Suárez, Hugo
%T On upper bounds for total $k$-domination number via the probabilistic method
%J Kybernetika
%D 2023
%P 537-547
%V 59
%N 4
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2023-4-0537/
%R 10.14736/kyb-2023-4-0537
%G en
%F 10_14736_kyb_2023_4_0537
Sigarreta, Saylí; Sigarreta, Saylé; Cruz-Suárez, Hugo. On upper bounds for total $k$-domination number via the probabilistic method. Kybernetika, Tome 59 (2023) no. 4, pp. 537-547. doi: 10.14736/kyb-2023-4-0537

[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

[2] Alon, N., Spencer, J H.: The Probabilistic Method. Wiley, New York 2016. | MR

[3] Bartle, R. G.: The Elements of Real Analysis. Wiley, New York 1991. | MR

[4] Cockayne, E J., Dawes, R. M., Hedetniemi, S. T.: Total domination in graphs. Networks 10 (1980),3, 211-219. | DOI | MR

[5] Haynes, T. W., Hedetniemi, S., Slater, P.: Fundamentals of Domination in Graphs. Marcel Dekker, New York 1998. | MR

[6] Henning, M. A., Kazemi, A. P.: $k$-tuple total domination in graphs. Discrete Appl. Math. 158 (2010), 9, 1006-1011. | DOI | MR

[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

[8] Henning, M. A., Yeo, A.: Total Domination in Graphs. Springer, New York 2013. | DOI | MR

[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

[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

Cité par Sources :