Domination éternelle dans les graphes
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.
Ensemble dominant Graph theory Graph protection Dominating set Fractional dominating set Eternal domination