On $k$-domatic numbers of graphs
Bohdan Zelinka · Czechoslovak Mathematical Journal · 1983
In [1] M. Borowiecki and M. Kuzak have generahzed the concept of a dominating set in a graph.Let G be an undirected graph without loops and multiple edges, let к be a positive integer.A /c-dominating set in the graph G is a subset D of the vertex set F(G) of G with the property that for each vertex x e V(^G) -D there exists a vertex y e D such that d{x, y) ^ k.(The symbol d(x, y) denotes the distance of the vertices X, y in the graph G.) For fe = 1 the /c-dominating sets are dominating sets in the usual sense.This leads to a generalization of the concept of the domatic number of a graph which was introduced by E. J. Cockayne and S. T. Hedetniemi in [2].A /c-domatic partition of G is a partition of F(G), all of whose classes are /c-dominating sets in G.The maximum number of classes of a /c-domatic partition of G is called the kdomatic number of G and denoted by dk{G).For /c = 1 we have ^^(G) = d(G), where d{G) is the domatic number of G.