Les problèmes de partitionnement dominant dans les graphes.

Abstract

Soit G = (V,E) un graphe simple d'ordre n où V est l'ensemble des sommets et E l'ensemble des arêtes. Le problème de partitionnement de G a pour objectif le découpage de G en sous graphes induits tout en satisfaisant certaines contraintes. Nous disons qu'un ensemble D C V est un ensemble dominant de G si chaque sommet de G est dans D ou adjacent à un sommet de D. Dans la littérature, ils existent plusieurs problèmes de partitionnement ayant une propriété additionnelle de domination, définie sur les sommets du graphe ou sur les parties de la partition. Dans ce mémoire, nous nous intéressons à ces problèmes. Nous citons, la partition domatique est une partition P de V(G) telle que chaque partie est un ensemble dominant de G. La partition dominante est une partition de V(G) telle que : Tout sommet est seul dans sa partie ou il est adjacent à tous les sommets d'une partie. La coloration dominante et la coloration stricte forte sont des cas particuliers de la partition dominante où toute partie induit un stable dans G. Nous rappelons ces différents problèmes en donnant leurs définitions, quelques exemples pratiques, quelques problèmes ouverts et les principaux résultats obtenus. Nous proposons la définition de deux nouveaux paramètres.