Domatic Numbe

The maximum number of disjoint dominating sets in a domatic partition of a graph  is called its domatic number .

The domatic number should not be confused with the domination number, which is the size of the smallest individual dominating set.

Let  be the minimum vertex degree of a graph , then

The domatic number of a graph with one or more isolated points is therefore 1.

Furthermore, if the domination number  of a graph  is known, than

where  denotes the vertex count of  and  is the floor function.

Finding the domatic number of a graph is computationally hard.

Given a complete set of minimal dominating sets, the domatic number of a graph  can be found as the independence number of the graph in which vertices are minimal dominating sets of  and edges exist between pairs sets having nonempty intersection.