Domatic number problem

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 "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

ources

* 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.


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Domatic number — A domatic partition. In graph theory, a domatic partition of a graph G = (V,E) is a partition of V into disjoint sets V1, V2,...,VK such that each Vi is a dominati …   Wikipedia

  • List of mathematics articles (D) — NOTOC D D distribution D module D D Agostino s K squared test D Alembert Euler condition D Alembert operator D Alembert s formula D Alembert s paradox D Alembert s principle Dagger category Dagger compact category Dagger symmetric monoidal… …   Wikipedia

  • Conjunto dominante — El conjunto dominante de un grafo G = (V, E) es un subconjunto V de V tal que cada vértice que no pertenezca a V está unido a (al menos) un miembro de V . El número dominante γ(G) es el cardinal del menor conjunto dominante de G. El problema de… …   Wikipedia Español

  • Nombre domatique — En théorie des graphes, le nombre domatique d un graphe est son nombre maximum d ensembles dominants disjoints deux à deux. Le problème du nombre domatique est de déterminer, en fonction d un graphe G et d un entier naturel k, si le nombre… …   Wikipédia en Français

  • Dominating set — For Dominator in control flow graphs, see Dominator (graph theory). Dominating sets (red vertices). In graph theory, a dominating set for a graph G = (V, E) is a subset D of V such that every vertex not in D is joined to at… …   Wikipedia

  • List of NP-complete problems — Here are some of the more commonly known problems that are NP complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP complete problems). Most of the problems in this list are taken… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”