Improved bounds on the \(k\)-tuple (Roman) domination number of a graph (Q2121485)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Improved bounds on the \(k\)-tuple (Roman) domination number of a graph |
scientific article |
Statements
Improved bounds on the \(k\)-tuple (Roman) domination number of a graph (English)
0 references
4 April 2022
0 references
\textit{M. A. Henning} and \textit{N. J. Rad} [ibid. 37, No. 1, 325--336 (2021; Zbl 1459.05239)] proposed several new probabilistic upper bounds on the \(k\)-tuple domination number, \(k\)-domination number, Roman domination number, and Roman \(k\)-domination number of a graph using the well-known Brooks' theorem for vertex coloring. In this paper, the authors use the well-known Turán's theorem, and give a slight improvement of all above given bounds. Their proofs follows closely the proofs given by Henning and Rad [loc. cit.], with the exception that instead of using Brooks' theorem to find a maximal independent set, they use Turán's theorem to find such a maximal independent set.
0 references
\(k\)-tuple domination
0 references
\(k\)-domination
0 references
Roman domination
0 references
Roman \(k\)-tuple domination
0 references
Turán's theorem
0 references