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 domatique de G est supérieur ou égal à k. C'est un problème NP-complet.
Exemple
Dans le graphe ci-contre, les trois ensembles de sommets (associés à chaque couleur) sont disjoints deux à deux, et dominants (par exemple pour l'ensemble jaune : tout sommet est soit jaune, soit voisin d'un jaune). Le nombre domatique du graphe vaut donc au moins 3 (en fait, il est exactement égal à 3).
DĂ©finitions Ă©quivalentes
Le nombre domatique de G est le plus grand entier n pour lequel il existe une partition de l'ensemble des sommets en n ensembles dominants.
Le problème du nombre domatique pour G et k revient à déterminer s'il existe k ensembles dominants disjoints deux à deux.
Complexité
Le problème du nombre domatique a été prouvé NP-complet par réduction mutuelle avec le problème 3SAT.
Références
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Domatic number problem » (voir la liste des auteurs).
- (en) Michael Garey et David S. Johnson, Computers and Intractability (en), W.H. Freeman, 1979. A1.1: GT2, p 190 (ISBN 0-7167-1045-5)
- (en) E. J. Cockayne et S. T. Hedetniemi, "Optimal domination in graphs", IEEE Trans. Circuits and Systems CAS-22, 855-857