Domatic number problem

From Wikipedia, the free encyclopedia

You have new messages (last change).

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

[edit] 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.

[edit] NP-complete

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

[edit] 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.
Retrieved from "http://en.wikipedia.org../../../d/o/m/Domatic_number_problem.html"