Contribution à l'étude des graphes u-excellents

Abstract

Soit un graphe simple G = (V, E). Un sous ensemble S de V est dit dominant de G si tout sommet de V − S possède au moins un voisin dans S. Le cardinal minimum d’un ensemble dominant de G, appelé nombre de domination de G, est noté γ(G) et tout ensemble dominant de cardinal γ(G) est appelé γ(G)-ensemble. D’autres types de domination sont définis en imposant une condition supplémentaire sur l’ensemble dominant. Par exemple, si on impose que tout sommet de G possède au moins deux voisins dans S, on aura la domination double et si on impose que les sommets du sous graphe induit par S sont couplés deux à deux, nous aurons la domination couplée. Pour tout paramètre µ(G), un ensemble dominant S de cardinal µ(G) vérifiant la propriété désirée est appelé µ(G)-ensemble. On dit que G est un graphe µ-excellent si tout sommet de G est contenu dans au moins un µ(G)-ensemble. Dans mémoire, on s’intéresse à l’étude de l’excellence des graphes par rapport à cer- tains paramètres de domination à l’aide de deux approches, la première est constructive, par contre la deuxième est basée sur la caractérisation des sommets qui ne sont dans aucun µ(G)-ensemble. Notre contribution dans ce domaine réside dans l’étude, par la deuxième approche, des arbres excellents par rapport à la domination double et la domination couplée. Ainsi, nous donnons une caractérisation des arbres excellents par rapport à ces deux types de domination.