On upper bounds for total $k$-domination number via the probabilistic method

Sigarreta, Saylí, Sigarreta, Saylé, and Cruz-Suárez, Hugo. "On upper bounds for total $k$-domination number via the probabilistic method." Kybernetika 59.4 (2023): 537-547. <http://eudml.org/doc/299492>.

@article{Sigarreta2023,
abstract = {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.},
author = {Sigarreta, Saylí, Sigarreta, Saylé, Cruz-Suárez, Hugo},
journal = {Kybernetika},
keywords = {domination; $k$-tuple total domination; probabilistic method},
language = {eng},
number = {4},
pages = {537-547},
publisher = {Institute of Information Theory and Automation AS CR},
title = {On upper bounds for total $k$-domination number via the probabilistic method},
url = {http://eudml.org/doc/299492},
volume = {59},
year = {2023},
}

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
PB - Institute of Information Theory and Automation AS CR
VL - 59
IS - 4
SP - 537
EP - 547
AB - 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.
LA - eng
KW - domination; $k$-tuple total domination; probabilistic method
UR - http://eudml.org/doc/299492
ER -