Domatic number

From Wikipedia, the free encyclopedia

In graph theory, the domatic number of a graph G = (V, E) is the maximum integer K such that V can be partitioned into K disjoint sets V1, V2,...,VK and such that each Vi is a dominating set for G.

[edit] See also

Domatic number problem

[edit] References

  • Garey, M. R. and D. S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, 1979. 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.html"