Semidomatic numbers of directed graphs
Bohdan Zelinka · Czech digital mathematics library · 1984
GRAPHS BOHDAN ZELINKAIn [1] E. J. Cockayne and S. T. Hedetniemi have introduced the concept of the domatic number of an undirected graph.In [2] this concept was transferred to directed graphs.Here we shall define two generalizations of the domatic numbers of directed graphs.Let G be a directed graph with the vertex setthere exists a vertex y e D such that the edge xy (or yx, respectively) belongs to G.An inside-domatic (or outside-domatic) partition of G is a partition of V(G), all of whose classes are inside-semidominating (or outside-semidominating) sets in G.The maximum number of classes of an inside-semidomatic (or outside-semidomatic) partition of G is called the inside-semidomatic (or outside-semidomatic) number of G and is denoted by d'(G) (or d*(G), respectively).Note that these numbers are defined for all directed graphs, because a partition of V(G) consisting of one class is simultaneously an inside-semidomatic partition of G and an outside-semidomatic one.Now a dominating set in a directed graph G can be defined as a subset of V(G) which is simultaneously inside-semidominating and outside-semidominating.The domatic number d(G) of G is the maximum number of classes of a domatic partition of G, i.e. of a partition, all of whose classes are dominating sets in G.This implies the following assertion.