Sur Quelques invariants de domination dans les graphes

Abstract

Nous nous sommes intéressés dans ce mémoire à l’étude de la domination forte et faible dans les graphes. Soit G = (V;E) un graphe simple d’ordre n, où V est l’ensemble des sommets et E l’ensemble des arêtes. Un sous ensemble D _ V est un dominant faible (resp, fort) de G si chaque sommet v 2 V 􀀀D est adjacent à un sommet u 2 D, où deg(v) _ deg(u) (resp. deg(v) _ deg(u)): Le cardinal minimum d’un ensemble dominant faible (resp, fort) de G est appelé le nombre de domination faible (resp, forte), noté par w(G) (resp, s(G)) de G. Dans ce mémoire, on commence par présenter quelques bornes supérieures sur les paramètres de domination forte et faible améliorant les bornes de Domke, Hattingh, Markus et Ungerer. Ainsi qu.une caractérisation des arbres pour lesquels le nombre de domination et le nombre de domination forte sont égaux. Dans un second lieu, nous montrons que si G est un graphe connexe d’ordre n _ 3; alors w(G) + ts(G) _ n; où t = 3 _+1 pour tout graphe G, t = 3 5 si G est un graphe bloc et t = 2 3 si G est un graphe sans griffes. En dernier lieu, nous étudions d.une façon brève la k-domination forte et faible dé.nie comme suit: Soit k _ 1 un entier. Un sous ensemble D _ V est un k-dominant fort (resp, faible) de G si tout sommet v de V 􀀀D est k-dominé fortement (resp. Faiblement) par un sommet de D. Le nombre de k-domination forte (resp. Nombre de k-domination faible); noté par ks (G) (resp, k w (G)) est le cardinal minimum d’un ensemble k-dominant fort (resp, faible) de G: Pour k = 1.on retrouve la définition de la domination forte et faible usuelle. Donc pour tout G.1s (G) = s (G) et 1 w (G) = w (G) : Quelques résultats intéressants sont obtenus dans ce sens, en particulier on présente quelques bornes et propriétés sur la k-domination forte et faible. On montre que pour tout graphe connexe G tel que s (G) _ 2 (resp, w (G) _ 2) et pour tout entier k _ 4, ks (G) < s (G) (resp, k w (G) < w (G)). On donne aussi une condition nécessaire pour les graphes G tels que 3s (G) = s (G) et nous caractérisons d.une façon descriptive des chenilles T telles que 3s (T) = s (T).