Domination éternelle dans les graphes

Abstract

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, à 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 à la relation entre le nombre de stabilité́, le nombre de domination éternelle et la cardinalité́ d’une couverture minimum d’un graphe dans le modè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.

In this thesis, we study the eternal domination problem in graphs. We consider three different models of the problem, namely the one-guard moves model, the all-guards move model and the fractional model. First of all, we study some fundamental questions related to the relation between the independence number, the eternal domination number and the clique cover number of a graph in the one-guard moves model. Second, we propose a strategy which gives an upper bound of mi/7 + O(m+n) on the eternal domination number of the strong grid Pm ⊠ Pn in the all-guards move model. In the end, inspired by the fundamental results in fractional graph theory, we introduce a fractional analogue of the eternal domination problem.