Etude des dominants localisateurs et des codes identifiants dans les graphes et quelques applications.

Abstract

Soit G = (V,E) un graphe simple d'ordre n où V est l'ensemble des sommets et E est l'ensemble des arêtes. Le problème de domination consiste à trouver un ensemble de sommets C tel que chaque sommet de V – C admet au moins un voisin dans C qu'on appelle un dominant, le cardinal minimum d'un ensemble dominant d'un graphe G est noté y(G) dit nombre de domination. D'une manière plus général, Un ensemble C SV est un dominant localisateur de G si C est un dominant de G et C sépare V – C. Un ensemble C SV est un code identifiant de G si C est un dominant de G et C sépare V. On désigne par Yı(G) la cardinalité minimale d'un dominant localisateur de G, et par Mı(G) la cardinalité minimale d'un code identifiant du graphe G, dit aussi nombre de code identifiant. Dans ce mémoire on a étudié la conjecture proposé par F. Foucaud qui concerne une borne supérieure du nombre de code identifiant à savoir : Mi Comme Yı(G) SM (G) on s'est demandé si elle est vraie pour le nombre de domination localisatrice. Par conséquent on s'est intéressé aux graphes dont la structure est simple pour vérifier sa validité.