Broadcast Domination et Broadcast Indépendance dans les Graphes.

Abstract

Soit G = (V, E) un graphe simple d'ordren où V est l'ensemble des sommets, et E est l'ensemble des arêtes. Une fonction f:V → [0,1, ..., diam(G)] est de broadcast sur G si pour tout sommet VEV, f(v) < e(v), où diam(G) représente le diamètre de G ete(G) représente l'excentricité du sommet v. On note par Vit l'ensemble des sommets v avec f(v) > 0. La somme des poids sur les sommets est représentée par of) = f(v);VEV). Une fonction broadcast est de domination ou dominante si tout sommet du graphe G se trouve au plus à une distance f(v) d'au moins un sommet v avec f(v) > 0. Le minimum de olf) sur toutes les fonctions broadcast de domination donne le nombre de broadcast dominant ou de domination du graphe, noté Yb(G). Une fonction broadcast f est dite indépendante si pour toute paire de sommets V, uelit, d(v, u) > max(f (v), f(u) où d(v,u) est la distance entre v et u (longueur de la plus courte chaine). Le poids maximum de olf) d'une fonction broadcast indépendante de G est le nombre de broadcast d'indépendance, noté Bb(G).Dans ce mémoire, on s'intéresse à la fonction broadcast dans les graphes simples. On commence notre travail par une présentation du paramètre « nombre de broadcast dominant », puis on s'intéresse au problème de recherche de la fonction de broadcast indépendante maximum , pour certaines classes de graphe. On détermine les valeurs du nombre de broadcast d'indépendance dans les cas où le graphe est une chaîne, un cycle ou une variante de chenille, comme la chenille pleine et la chenille alternée. On détermine, aussi quelques bornes qui encadrent notre paramètre.