The Domatic Numbers of Factors of Graphs

Abstract

The maximum cardinality of a partition of the vertex set of a graph $G$ into dominating sets is the domatic number of $G$, denoted $d(G)$. We consider Nordhaus-Gaddum type results involving the domatic number of a graph, where a Nordhaus-Gaddum type result is a (tight) lower or upper bound on the sum or product of a parameter of a graph and its complement. Thereafter we investigate the upper bounds on the sum and product of the domatic numbers $d(G_1),d(G_2)$ and $d(G_3)$ where $G_1\oplus G_2\oplus G_3=K_n$. We show that the upper bound on the sum is $n+2$, while the maximum value of the product is $\lceil \frac{n}{3}{\rceil }^3$ for $n>57$.