Domination éternelle dans les graphes
Le présent mémoire traite du problème de domination éternelle dans les graphes. Nous considérons trois modèles différents du problème, à savoir le modèle du garde, de l’anglais one-guard moves model, le modèle des gardes, de l’anglais all-guards move model, et le modèle fractionnaire. Dans un premier temps, nous étudions quelques questions fondamentales liées à la relation entre le nombre de stabilité́, le nombre de domination éternelle et la cardinalité́ d’une couverture minimum d’un graphe dans le modèle du garde. Dans un second temps, nous proposons une stratégie qui borne supérieurement par mi/7 + O(m+n) le nombre de domination éternelle de la grille forte Pm ⊠ Pn dans le modèle des gardes. Finalement, nous nous inspirons de quelques résultats de la théorie fractionnaire des graphes pour introduire une analogue fractionnaire du problème.
Théorie des graphes Protection de graphes Ensemble dominant fractionnaire Domination éternelle