Generalized k-Rainbow and Generalized 2-Rainbow Domination in Graphs

Document Type : Research Paper


1 University of Qom

2 Department of Mathematics, Farahan Branch, Islamic Azad University Farahan, Iran.

3 Department of Mathematics, Faculty of Sciences, University of Qom Qom, IRAN.



Assume we have a set of k colors and to each vertex of a graph G we assign an arbitry of these colors. If we require that each vertex to set is assigned has in its closed neighborhood all k colors, then this is called the generalized k-rainbow dominating function of a graph G. The corresponding γgkr, which is the minimum sum of numbers of assigned colores over all vertices of G, is called the gk-rainbow domination number of G. In this paper we present a linear algorithms for determining a minimum generalized 2-rainbow dominating set of a tree and on GP(n,2).