Abstract
Rautenbach and Volkmann (Appl Math Lett 20:98–102, 2007), gave an upper bound for the k-tuple domination number of a graph. Rad (J Combin Math Comb Comput, 2019, in press) presented an improvement of the above bound using the Caro-Wei Theorem. In this paper, using the well-known Brooks’ Theorem for vertex coloring and vertex covers, we improve the above bounds on the k-tuple domination number under some certain conditions. In the special case k= 1 , we improve the upper bounds for the domination number (Arnautov in Prikl Mat Program 11:3–8, 1974; Payan in Cahiers Centre Études Recherche Opér 17:307–317, 1975) and the Roman domination number (Cockayne et al. in Discrete Math 278:11–22, 2004). We also improve bounds given by Hansberg and Volkmann (Discrete Appl Math 157:1634–1639, 2009) for Roman k-domination number, and Rad and Rahbani (Discuss Math Graph Theory 39:41–53, 2019) for double Roman domination number.
Original language | English |
---|---|
Pages (from-to) | 325-336 |
Number of pages | 12 |
Journal | Graphs and Combinatorics |
Volume | 37 |
Issue number | 1 |
DOIs | |
Publication status | Published - Jan 2021 |
Keywords
- Brooks’ Theorem
- Roman domination
- Vertex cover
- k-Tuple domination
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics