Le jeu de domination dans les graphes

Comme cela avait été fait depuis longtemps pour la coloration, un jeu de domination a été proposé en 2010. Deux joueurs jouent tour à tour sur un graphe. Chaque coup consiste à sélectionner un sommet et à ajouter ses voisins à l’ensemble des sommets dominés du graphe, initialement vide. Un coup n’est légal que s’il accroit effectivement l’ensemble des sommets dominés. Lorsque le graphe est entièrement dominé et donc qu’aucun coup restant n’est légal, on définit le score de la partie par le nombre de coups joués conjointement, c’est-à-dire la taille de l’ensemble dominant du graphe construit.

Les joueurs ont des objectifs antagonistes, Dominator veut minimiser le score et Staller s’évertue à le maximiser. Le nombre de domination ludique d’un graphe est le score obtenu lorsque les deux joueurs jouent de façon optimale. Deux variantes du paramètres sont étudiées, selon qui ouvre le jeu. Nous nous intéresserons à quelques résultats généraux sur le problème, notamment sur les graphes présentant des propriétés spécifiques pour ce jeu, et aux liens entre les deux variantes.