Sur Les ensembles dominants localisateurs(totaux) dans les graphes

Abstract

Nous nous sommes intéressés dans ce mémoire à l’étude de la domination localisatrice dans les graphes. Soit G = (V, E) un graphe simple, d’ensemble de sommets V et d’ensemble d’arêtes E. Un sous ensemble S de V est dit dominant de G si tout sommet de V–S est adjacent à au moins un sommet de S. Un ensemble dominant S est dit localisateur si pour toute paire de sommets u,v de V–S, N(u)∩ S≠ N(v) ∩ S. Le nombre de domination localisatrice de G, noté par (G) L γ est le cardinal minimum d’un ensemble dominant localisateur de G, et le nombre de domination localisatrice supérieur, noté par ΓL ( ) G est le cardinal maximum d’un ensemble dominant localisateur minimal (au sens de l’inclusion) de G. Un dominant localisateur S de G est dit total si tout sommet de S possède un voisin dans S. Le nombre de domination localisatrice totale de G, noté par L t γ (G) est le cardinal minimum d’un ensemble dominant localisateur total de G. Dans un premier lieu, nous nous sommes intéressés au paramètre ΓL , étant donné qu’aucune étude n’a été réalisée jusqu’à présent (à notre connaissance) sur ce paramètre. Nous montrons que tout ensemble indépendant maximum est un dominant localisateur minimal pour tout arbre, ou pour tout graphe G de maille supérieure ou égale à 5. Nous présentons aussi quelques bornes sur ΓL , ainsi qu’une caractérisation des graphes extrémaux pour certaines d’entre elles. Dans un second lieu, nous exposons quelques résultats obtenus sur le paramètre de domination localisatrice L γ , en établissant des extensions de quelques bornes déjà existants pour certaines classes de graphes (les bipartis, les unicycles et les graphes cactus). Nous déterminons aussi une relation liant L γ à d’autres paramètres de domination 2 γ , ρ,γ . En dernier lieu, nous étudions d’une façon brève le paramètre de domination localisatrice totale, où quelques résultats partiels sont obtenus.