Contribution à l'étude de la yl-excellence et de la yl-unicité dans les arbres

Abstract

Soit G = ÝV,EÞ un graphe simple. Le voisinage ouvert d’un sommet u de V est NÝuÞ = áv 5 V P uv 5 Eâ. Un sous enemble S de V est un ensemble 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, noté LÝGÞ, est appelé le nombre de domination de G. Un dominant de G de taille LÝGÞ est un LÝGÞ-ensemble. Si on impose une condition sur les sommets de S, on définit d’autres types de domination. Le voisinage dans S d’un sommet u de V ? S est noté NÝuÞ V S. Un ensemble dominant S de G est un ensemble dominant localisateur de G si pour toute paire de sommets x, y de V ? S, NÝxÞ V S ® NÝyÞ V S. Le nombre de domination localisateur de G est noté LLÝGÞ. Un graphe G est dit LL-excellent si tout sommet de G est contenu dans au moins un LLÝGÞ-ensemble. Dans ce mémoire on s’intéresse à l’étude de la LL-excellence et la LL-unicité dans les arbres. Dans mon travail on a donné une caractérisation des arbres LL-excellents, basée sur la définition de l’ensemble des sommets n’appartenant à aucun LLÝTÞ-ensemble noté par NLÝTÞ. On a proposé ensuite une caractérisation constructive des arbres ayant un LLÝTÞ-ensemble unique. Enfin on a montré que dans le cas des arbres LLÝTÞ ² Ýn + l ? sÞ 2 ² KÝTÞ ² L2ÝTÞ et on a caractérisé les arbres extrémaux.