Evènement pour le groupe GT Graphes et Applications


Date 2013-11-08  14:00-15:00
TitreJeu de domination et graphes no-minus 
RésuméLe jeu de domination est un jeu a deux joueurs dont le plateau est un graphe fini sur lequel les joueurs construisent un ensemble dominant. Les joueurs choisissent chacun leur tour un sommet qui domine au moins un nouveau sommet et l’ajoutent a l’ensemble. Le jeu se termine lorsque l’ensemble ainsi construit forme un ensemble dominant. Un des joueurs, Dominator, a pour but d’arriver a un ensemble le plus petit possible, alors que l’autre joueur, Staller, essaie d’en maximiser la taille. Le nombre de domination ludique, noté γ_g , est la taille de cet ensemble lorsque les deux joueurs jouent de façon optimale et que Dominator commence la partie. On note γ'_g le paramètre défini de la même manière en considérant que Staller commence la partie. On s’intéresse ici a une classe de graphes pour laquelle on a toujours γ_g ≤ γ'_g , qu’on appelle les graphes “no-minus”, et dont le comportement vis-à-vis du jeu de domination est plus prévisible que dans le cas général. En particulier, on montre que les graphes “tri-split” et les graphes “dually-chordal” sont des graphes “no-minus”. 
LieuSalle 178 
OrateurGabriel Renault 



Aucun document lié à cet événement.

Retour
Retour à l'index