Contribution a l'étude de la domination romaine faible dans les graphes modifies

Abstract

Soit G = (V; E) un graphe. Si f est une fonction dØ nie de V dans f0; 1; 2g, alors un sommet v avec f(v) = 0 est dit non dØfendu (non protØgØ) par rapport à f s il n est pas adjacent à un sommet w avec f(w) > 0. Une fonction de domination romaine faible (FDRF) est une fonction f : V ! f0; 1; 2g vØri ant pour tout sommet v avec f(v) = 0 il existe un voisin w avec f(w) > 0 et la fonction f 0 = (V 0 0 ; V 0 1 ; V 0 2 ) dØ nie par f (v) = 1, f 0 (w) = f(w)1, et f 0 (u) = f(u) pour tout sommet u 2 V fv; wg, n a pas de sommet non dØfendu. Le poids d une FDRF est la valeur f(V ) = X f(u) et le nombre de domination Romaine faible,

r v2V (G) est le poids minimum d une FDRF de G: Dans ce mØmoire, nous nous sommes intØressØes à l Øtude de l e⁄et de la suppression d une arŒte d un graphe sur le paramŁtre

(G), oø il a ØtØ montrØ que la suppression d une arŒte e de G ne fait pas diminuer le paramŁtre

r (G); mais peut l augmenter d au plus une unitØ. Ainsi, le rØsultat principal de ce mØmoire a ØtØ de donner une caractØrisation constructive de tous les arbres dont la suppression d une arŒte quelconque fait augmenter le nombre de domination Romaine faible.