Skip to main content
General Bounds on Rainbow Domination Numbers
Graphs and Combinatorics
  • Shinya Fujita, Maebashi Institute of Technology, Maebashi, Japan
  • Michitaka Furuya, Tokyo University of Science
  • Colton Magnant, Georgia Southern University
Document Type
Publication Date

A k-rainbow dominating function of a graph G is a function f from the vertices V(G) to 2{1,2,…,k} such that, for all v∈V(G), either f(v)≠∅ or ⋃u∈N[v]f(u)={1,2,…,k}. The k-rainbow domination number of a graph G is then defined to be the minimum weight w(f)=∑v∈V(G)|f(v)| of a k-rainbow dominating function. In this work, we prove sharp upper bounds on the k-rainbow domination number for all values of k. Furthermore, we also consider the problem with minimum degree restrictions on the graph.

Citation Information
Shinya Fujita, Michitaka Furuya and Colton Magnant. "General Bounds on Rainbow Domination Numbers" Graphs and Combinatorics Vol. 31 Iss. 3 (2015) p. 601 - 613 ISSN: 1435-5914
Available at: