Contribution à l'étude de la 2-domination dans les arbres, V2-excellence et autres.

Abstract

Soit G = (V, E) un graphe simple. Un dominant de G est un sous ensemble S de V tel que tout sommet de V - S possède au moins un voisin dans S. L'ordre minimum d'un ensemble dominant de G, appelé nombre de domination de G, et est noté y(G). On peut définir d'autres types de domination si on impose une ou plusieurs) condition (s) supplémentaire sur l'ensemble dominant. Par exemple, si on impose la condition que tout sommet de V - S possède au moins k voisins dans S, on obtient la k-domination. Pour tout paramètre (G), un ensemble dominant S de cardinal (G) vérifiant la propriété désirée est appelé (G)-ensemble. Si on dit qu'un sommet est dans tout ou dans aucun (G)-ensemble, alors on caractérise ce sommet. On dit qu'un graphe G est j-excellent si tout sommet de V est contenu dans au moins un (G)-ensemble. Dans ce mémoire, on s'intéresse à l'étude de l'excellence des graphes par rapport à la 2-domination, en suivant l'approche qui consiste à caractériser les sommets qui sont tout ou dans aucun y2(G)-ensemble. Notre contribution dans ce mémoire consiste à caractériser les arbres excellents par rapport à la 2-domination. Enfin, on établit un algorithme de reconnaissance des arbres y2-excellents, les arbres y2-recommandables, les arbres y2 indésirables et les arbres y2-justes.