## Abstract

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 language | English |
---|---|

Pages (from-to) | 213-225 |

Number of pages | 13 |

Journal | Taiwanese Journal of Mathematics |

Volume | 12 |

Issue number | 1 |

DOIs | |

Publication status | Published - Feb 2008 |

Externally published | Yes |

## Keywords

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

## ASJC Scopus subject areas

- General Mathematics