La Domination 1-mobile dans les graphes.

Abstract

Dans ce mémoire, nous nous intéressons à la sécurité dans les graphes. Une stratégie de protection d'un graphe consiste à placer des gardiens au chevet des sommets afin de protéger le graphe contre d'éventuelles attaques. Dans la littérature, plusieurs variantes de ces problèmes de protection ont été étudiées. Nous présentons la domination 1-mobile où un gardien au plus est placé dans un sommet. Lorsqu'un gardien est attaqué, il est neutralisé ou peut se déplacer à un sommet voisin de sorte que le placement des gardiens forme, avant et après l'attaque, un dominant du graphe. 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 1 mobile et sa cardinalité minimum est dite nombre de domination l-mobile. Nous rappelons les résultats de la littérature concernant la domination 1-mobile et deux concepts de sécurité similaires. Nous rappelons également les résultats de quatre variantes de la domination 1-mobile. Nous contribuons à l'étude du sujet par des résultats sur le nombre de domination 1-mobile et sa variante indépendante.