Domatic number problem

The domatic number problem is an NP-complete problem in graph theory.

Definition

An instance of the domatic number problem consists of:

• a graph G with a set V of vertices and a set E of edges, and
• a positive integer K smaller than or equal to the number of vertices in G.

The problem is to determine whether the domatic number of G is at least K. In other words, we want to know if V can be partitioned into k ≤K disjoint sets V₁, V₂,...,V_k such that each V_i is a dominating set for G.

NP-complete

The domatic number problem is proven to be NP-complete by a reduction from the 3-Satisfiability problem.

References

• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A1.1: GT3, pg.190.
• Garey, M. R., D. S. Johnson and R. E. Tarjan, unpublished results.
• Cockayne, E. J., and S. T. Hedetniemi, "Optimal domination in graphs", IEEE Trans. Circuits and Systems CAS-22, 855-857.