On the {k}-domatic number of graphs

Abstract

For a positive integer k, a {k}-dominating function of a graph G is a function/from the vertex set V(G) to the set {0,1,2,...,k} such that for any vertex v ∈ V(G), the condition Σu∈N[v] f(u) ≥ k is fulfilled, where N[v] is the closed neighborhood of v. The {1}-dominating function is the same as the ordinary domination. A set {f₁, f₂,..., f_d} of distinct {k}-dominating functions on G with the property that Σ^d_i=1 f_i(v) ≤ k for eacn v ∈ V(G), is called a {k}-dominating family (of functions) on G. The maximum number of functions in a {k}-dominating family on G is the {k}-domatic number of G, denoted by d_{k}(G). Note that d_{k}(G) is the classical domatic number d(G). In this paper we continue the study of the {k}-domatic number in graphs. In particular, we present bounds for the {k}-domatic number, and we determine the {k}-domatic number of cylinders.