Rainbow domination in graphs

Boštjan Brešar, Michael A. Henning, Douglas F. Rall

Research output: Contribution to journalArticlepeer-review

150 Citations (Scopus)


Assume we have a set of k colors and to each vertex of a graph G we assign an arbitrary subset of these colors. If we require that each vertex to which an empty set is assigned has in its neighborhood all k colors, then this is called the k-rainbow dominating function of a graph G. The corresponding invariant γrk(G), which is the minimum sum of numbers of assigned colors over all vertices of G, is called the k-rainbow domination number of G. In this paper we connect this new concept to usual domination in (products of) graphs, and present its application to paired-domination of Cartesian products of graphs. Finally, we present a linear algorithm for determining a minimum 2-rainbow dominating set of a tree.

Original languageEnglish
Pages (from-to)213-225
Number of pages13
JournalTaiwanese Journal of Mathematics
Issue number1
Publication statusPublished - Feb 2008
Externally publishedYes


  • Cartesian product
  • Domination
  • Paired-domination
  • Vizing's conjecture

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'Rainbow domination in graphs'. Together they form a unique fingerprint.

Cite this