The k-rainbow domatic number of a graph

Seyyed Mahmoud Sheikholeslami ; Lutz Volkmann

Discussiones Mathematicae Graph Theory, Tome 32 (2012) no. 1, p. 129.

Résumé

For a positive integer k, a k-rainbow dominating function of a graph G is a function f from the vertex set V(G) to the set of all subsets of the set 1,2, ...,k such that for any vertex v ∈ V(G) with f(v) = ∅ the condition ⋃u ∈ N(v)f(u) = 1,2, ...,k is fulfilled, where N(v) is the neighborhood of v. The 1-rainbow domination is the same as the ordinary domination. A set f ₁ , f ₂ , . . . , f d of k-rainbow dominating functions on G with the property that ∑ i = 1 d | f i ( v ) | ≤ k for each v ∈ V(G), is called a k-rainbow dominating family (of functions) on G. The maximum number of functions in a k-rainbow dominating family on G is the k-rainbow domatic number of G, denoted by d r k ( G ) . Note that d r 1 ( G ) is the classical domatic number d(G). In this paper we initiate the study of the k-rainbow domatic number in graphs and we present some bounds for d r k ( G ) . Many of the known bounds of d(G) are immediate consequences of our results.

Détail

Classification : 05C69
Mots-clés : k-rainbow dominating function, k-rainbow domination number, k-rainbow domatic number, -rainbow dominating function, -rainbow domination number, -rainbow domatic number