Etude de la a-Domination dans les Graphes.

Abstract

Dans ce mémoire, on s'intéresse essentiellement au paramètre cr-domination dans les graphes. Un sous-ensemble S de V est un a-dominant de G, si tout sommet 2 EV-S est adjacent à au moins a N() sommets dans S pour 0 < a < 1. Le cardinal minimum d'un ensemble a-dominant de G, est noté par Ya(G), est appelé le nombre de a-domination. Ce mémoire comprend deux parties. Dans la première partie, on s'intéresse à l'étude de la détermination de la valeur exacte du nombre cx-domination dans les graphes tripartis complets et la détermination des valeurs exactes et des bornes supérieures du nombre a-domination dans le graphe du Roi, aussi on considère des résultats relatifs aux arbres. Par la suite, on établit le nombre de a-domination de certaines classes des graphes. Ces classes comprennent le graphe roue, le graphe soleil, le graphe éventail, le graphe milieu, le graphe total et le graphe adjoint de quelques familles de graphes simples. Dans la deuxième partie, nous abordons le problème de la criticité. On s'est intéressé essentiellement à la suppression d'un sommet du graphe. On propose des résultats quand la suppression d'un sommet laisse la valeur du nombre de c-domination stable c-à-d la valeur de c-domination ne change pas.