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

Cité par Sources :