Résumé:
Soit G = (V; E) un graphe simple. Une Fonction de domination Romaine double
(FDRD) de G est une fonction f : V (G) ! f0; 1; 2; 3g telle que :
i) Chaque sommet v 2 V avec f(v) = 0 est adjacent à : au moins deux sommets v
2 V
tel que f(v
1
) = f(v
2
) = 2; ou à au moins un sommet v
3
2 V tel que f(v
ii) Chaque sommet v avec f(v) = 1 est adjacent à au moins un sommet w avec f(w) 2:
Le poids d une FDRD est la valeur f(v) =
P
f(u). Le nombre de domination
Romaine double de G, notØ par
dR
u2v
(G), est le poids minimum d une FDRD sur G:
Dans ce mØmoire, on s intØresse à l Øtude de l e⁄et de la subdivision des arŒtes dans
un graphe G sur le nombre de domination Romaine double
(G); oø on dØtermine le
nombre minimum d arŒtes que l on doit subdiviser pour augmenter
dR
(G). Ce nombre
est notØ par sd
dR
(G); et il est toujours supØrieur ou Øgal à 1.
dR
3
1
; v
) = 3.
2
