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 V1, V2,...,Vk such that each Vi 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
- Garey, M. R. and D. S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, 1979.
- 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.
Last updated: 05-29-2005 09:11:47
