Sur Quelques Invariants De Domination Dans Les Graphes

Résumé: 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 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 Dans ce mÈmoire, on commence par prÈsenter quelques bornes superieures 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 dominaton forte sont Ègaux.Dans un second lieu, nous montrons que si G est un graphe connexe díordre n ? 3; alors ?w(G) + t?s(G) ? n; o? t = ?+13 pour tout graphe G, t = 35 si G est un graphe bloc et t = 32 si G est un graphe sans gri§es. 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 ?sk (G) (resp, ?wk (G)) est le cardinal minimum díun ensemble k-dominant fort (resp, faible) de G: Pour k = 1Çon retrouve la dÈÖnition de la domination forte et faible usuelle. Donc pour tout GÇ?s1 (G) = ?s (G) et ?w1 (G) = ?w (G) : Quelques rÈsultats intÈrÈssants 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, ?sk (G) < ?s (G) (resp, ?wk (G) < ?w (G)). On donne aussi une condition nÈcÈssaire 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

Publié dans la revue: