ON INTEGER DOMINATION IN GRAPHS AND VIZING-LIKE PROBLEMS

We continue the study of fkg-dominating functions in graphs (or integer domination as we shall also say) started by Domke, Hedet- niemi, Laskar, and Fricke (5). For k ‚ 1 an integer, a function f : V (G) ! f0;1;:::;kg defined on the vertices of a graph G is called a fkg-dominating function if the sum of its function values over any closed neighborhood is at least k. The weight of a fkg-dominating function is the sum of its function values over all vertices. The fkg-domination number of G is the minimum weight of a fkg-dominating function of G. We study the fkg-domination number on the Cartesian product of graphs, mostly on problems related to the famous Vizing's conjecture. A connection be- tween the fkg-domination number and other domination type parameters is also studied.