A sufficient condition for large rainbow domination number

摘要

Let k be a positive integer, and set [k] := {1,2,...,k}. Let G be a graph. A k-rainbow dominating function (or k-RDF) of G is a function f from V(G) to2~([k]) such that for a vertex v ∈ V(G) with f(v) = Ø, the condition ∪_(u∈N_G(v)) f(u) = [k] is fulfilled, where N_G(v) is the open neighbourhood of v. The weight of k-RDF f of G is the value ω(f) := ∑_(v∈V(G)) |f(v)|.The k-rainbow domination number of G, denoted by γ_(rk)((G), is the minimum weight of a k-RDF of G. We focus on two results (here ∆(G) denote the maximum degree of G): (i) If a graph G satisfies k > ∆(G)~2, then γ_(rt)(G) = |V(G)| (proved in Z. Shao, M. Liang, C. Yin, X. Xu, P. Pavlic, and J. Zerovnik, On rainbow domination numbers of graphs, Inform. Sci. 254 (2014), pp. 225-234). (ii) For any graphs G, γ_(rk)(G) ≥ k|V(G)|/(∆(G) + k) (proved in D. Meierling, S.M. Sheikholeslami, and L. Volkmann, Nordhaus-Gaddum bounds on the k-rainbow domatic number of a graph, Appl. Math. Lett. 24 (2011), pp. 1758-1761). In this paper, we give a common improvement of (i) and (ii) for the case where k > ∆(G), and prove that γ_(rk)(G) ≥ min{k|V(G)|/2∆(G),|V(G)|). Moreover, by partially using the above result, we also obtain a Nordhaus-Gaddum inequality for the k-rainbow domination number and the k-rainbow domination number of ladders P_2□P_n.