Domination éternelle dans les graphes
Thesis or Dissertation
Abstract(s)
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.
This document disseminated on Papyrus is the exclusive property of the copyright holders and is protected by the Copyright Act (R.S.C. 1985, c. C-42). It may be used for fair dealing and non-commercial purposes, for private study or research, criticism and review as provided by law. For any other use, written authorization from the copyright holders is required.