Skip to main content
General Bounds on Rainbow Domination Numbers
Graphs and Combinatorics (2013)
  • Shinya Fujita
  • Michitaka Furuya
  • Colton Magnant, Georgia Southern University

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 vV(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.

  • Rainbow domination number,
  • k-rainbow dominating function,
  • Minimum degree
Publication Date
December 29, 2013
Citation Information
Shinya Fujita, Michitaka Furuya and Colton Magnant. "General Bounds on Rainbow Domination Numbers" Graphs and Combinatorics (2013)
Available at: