Upper Bounds on the k-Tuple (Roman) Domination Number of a Graph

Nader Jafari Rad | Michael A. Henning

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=158315
Date :  2021/02/21
Publish in :    Graphs and Combinatorics
DOI :  https://doi.org/https://doi.org/10.1007/s00373-020-02249-7
Link :  http://dx.doi.org/https://doi.org/10.1007/s00373-020-02249-7
Keywords :Rautenbach and Volkmann

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.