The Domatic Number of Regular Graphs

Abstract

The domatic number of a graph $G$ is the maximum number of dominating sets into which the vertex set of $G$ can be partitioned.

We show that the domatic number of a random $r$-regular graph is almost surely at most $r$, and that for $3$-regular random graphs, the domatic number is almost surely equal to $3$.

We also give a lower bound on the domatic number of a graph in terms of order, minimum degree, and maximum degree. As a corollary, we obtain the result that the domatic number of an $r$-regular graph is at least $(r+1)/(3ln(r+1))$.