Sur le nombre de subdivision de la domination romaine double

Abstract

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