Titre : On a modular domination game

Auteurs : Sylvain. Gravier, Mehdi Mhalla, Eric Tannier

Abstract:
We present a generalization of the so called $\sigma$-game, introduced by Sutner (Linear cellular automata and the Garden-of-Eden in Math. Intelligencer 11, (1989) 49-53), a combinatorial game played on a graph, with relations to cellular automata, as well as odd domination in graphs.
A configuration on a graph is an assignment of values in $\{0, \ldots, p-1\}$ (where $p$ is an arbitrary positive integer) to all the vertices of $G$. One may think of a vertex $v$ of $G$ as a button the player can press at his discretion. If vertex $v$ is chosen, the value of all the vertices adjacent to $v$ increases
by $1$ modulo $p$. This defines a equivalence relation between the configurations: two configurations are in relation if it is possible to reach one from the other by a sequence of such operations. We investigate the number of equivalence classes a given graph has, and give formula for trees and special regular graphs.