Graphes domination double point stables.

Abstract

Un sous ensemble de sommets S d'un graphe simple G = (V, E) est dit double dominant de G, si tout sommet de V - S possède au moins deux voisins dans S et tout sommet de S possède au moins un voisin dans S. Le cardinal minimum d'un ensemble double dominant de G est appelé nombre de domination double de G, noté par 7x2(G). On s'intéresse dans ce mémoire à l'étude de l'effet de l'identification de deux sommets quelconques dans G. Quelques propriétés sont établies, en particulier on donne une caractérisation constructive des arbres T tels que "x2(Tuv) = x2(T) pour tout couple de sommets adjacents de T.