La Domination sécurisée et totale sécurisée dans les graphes.

Abstract

Dans ce mémoire, nous nous intéressons aux concepts de la protection dans les graphes. Une stratégie de protection d'un graphe consiste à placer des gardiens au chevet de chaque sommet afin de le défendre contre une éventuelle attaque. Dans la littérature, plusieurs variantes de ces problèmes de protection ont été étudiées. Nous présentons la domination sécurisée où un gardien au plus est placé dans un sommet. Lorsqu'un sommet sans gardien est attaqué, un gardien sur un sommet voisin peut se déplacer pour le défendre. Nous cherchons à utiliser le minimum de gardiens tel que l'ensemble des gardiens forme, avant et après l'attaque, un dominant du graphe. Un tel ensemble est dit dominant sécurisé et sa cardinalité minimum est dite nombre de domination sécurisée. Si de plus un sommet avec gardien doit être protégé par un autre gardien, nous parlons alors de la domination sécurisée totale. Dans ce mémoire, nous considérons ces concepts et nous reprenons les résultats de la littérature, en particulier les questions ouvertes. Nous contribuons à l'étude du sujet également par des résultats de bornes sur le nombre de domination sécurisée.