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

Michael A. Henning, Nader Jafari Rad

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

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 languageEnglish
Pages (from-to)325-336
Number of pages12
JournalGraphs and Combinatorics
Volume37
Issue number1
DOIs
Publication statusPublished - Jan 2021

Keywords

  • Brooks’ Theorem
  • Roman domination
  • Vertex cover
  • k-Tuple domination

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Upper Bounds on the k-Tuple (Roman) Domination Number of a Graph'. Together they form a unique fingerprint.

Cite this