Abstract FR:

La theorie des graphes est un domaine faisant le lien entre les mathematiques discretes et l'informatique. Une question provenant de la modelisation de problemes tres concrets (par exemple reseaux de transports, de telephone, de microprocesseurs etc. . . ) peut etre etudiee par des methodes purement abstraites et etre appliquee en retour par des utilisateurs potentiels dans le domaine qui lui a donne naissance ou dans n'importe quel autre domaine. Les parametres de domination qui nous interessent depuis plusieurs annees interviennent en particulier dans des problemes de communication dans les reseaux, par exemple pour optimiser la localisation ou la puissance d'emetteurs ou de relais intermediaires. Dans cette these, nous ne considerons que l'aspect theorique de ces problemes. Comme les parametres de domination sont difficiles a determiner exactement (problemes np-complets), nous recherchons des inegalites entre certains d'entre eux ainsi que des conditions permettant d'obtenir l'egalite. Une autre approche, classique dans les problemes d'optimisation combinatoire portant sur des entiers, est d'essayer de trouver une bonne approximation fractionnaire en fonction du nombre de sommets du graphe.