Contribution à l'étude de quelques problèmes de domination dans les graphes

Abstract

Notre travail dans cette these porte sur ltude de la domination localisatrice dans les graphes. Soit G = (V; E) un graphe simple, o? V est lensemble des sommets et E est lensemble des artes. Un sous-ensemble S de V est dit ensemble dominant de G si tout sommet de V S est adjacent ‡ au moins un sommet de S: Si, de plus, pour toute paire de sommets u et v dans V S; les ensembles N (u) \ S et N (v) \ S sont distincts, alors S est appele ensemble dominant localisateur de G: Nous notons par L (G) (respectivement, L (G)) le cardinal minimum (respectivement, maximum) dun ensemble dominant localisateur (respectivement, dominant localisateur minimal) de G: La contraction dune arte uv dans un graphe G consiste ‡ supprimer les sommets u et v de G en les remplaÁant par un nouveau sommet not par uv; et en attachant uv ‡ tous les sommets qui sont adjacents ‡ u ou v dans G: Le graphe obtenu ‡ partir de G en contractant larte uv est not par Guv: Un graphe G est dit L-point-critique si L (Guv) < L (G) pour toute arte uv dans E: Etant donn un entier k > 0; un graphe G est dni comme tant kL-point-critique si L (G) = k et G est un graphe L-point-critique. Notre contribution dans cette these est divisie en deux parties distinctes. Dans la premiere partie, nous caractrisons tous les graphes connexes 3-L-point-critiques. Dans la deuxime partie, notre attention est portue sur le nombre de domination localisatrice superieur en donnant quelques rsultats intermdiaires avant de caractriser tous les graphes connexes dordre n 4 tels que L (G) = n-2