Sur le nombre de subdivision de la domination 2-rainbow.

Abstract

Supposons que nous avons un ensemble de 2 couleurs et à chaque sommet v d'un graphe G=(V, E), nous attribuons un sous-ensemble de ces couleurs. Si nous exigeons que chaque sommet pour lequel nous avons atribué un ensemble vide il faut que dans son voisinage les 2 couleurs soient attribuées. C'est à dire, on a une application f : V(G) + P({1,2}) tel que pour tout v € V(G) ayant f(v) = 0 on a U f(u) = {1,2}. C'est ce qu'on appelle WEN() la fonction de domination 2-Rainbow d'un graphe G. Le paramètre correspondant 72(G), qui est le minimum de la somme des nombres de couleurs attribuées sur tous les sommets de V(G), est appelé le nombre de domination 2-Rainbow de G. Dans ce mémoire, nous nous sommes interessés à l'étude de l'effet de la subdivision des arêtes de G où on détermine le nombre minimum d'arêtes que l'on doit subdiviser pour faire augmenter Yr2(G). Ce nombre est noté par sdy (G), il est toujours supérieur ou égal à 1.