Domatic Number

Input

Graph $G = (V, E)$, positive integer $K \leq |V|$.

Question

Is the domatic number of $G$ at least $K$, i.e. can $V$ be partitioned into $k \geq K$ disjoint sets $V_1, V_2, \dots, V_k$ such that each $V_i$ is a dominating set for $G$?

Classes

• NP-complete

Comments

Remains NP-complete for any fixed $K \geq 3$. (The domatic number is always at least 2 unless $G$ contains an isolated vertex.)

Proofs

NP-complete

Transformation from 3-Satisfiability. The problem is discussed in (Cockayne & Hedetniemi, 1975).

Reducible from

• 3-Satisfiability

References

• Cockayne, E., & Hedetniemi, S. (1975). Optimal domination in graphs. IEEE Transactions on Circuits and Systems, 22(11), 855–857. https://doi.org/10.1109/tcs.1975.1083994