Résumé | The distinguishing number of a graph G is a symmetry related graph invariant whose study started a decade ago. The distinguishing number D(G) is the least integer d such that G has a d-distinguishing coloring. A d-distinguishing coloring is a coloring c : V(G)-->{1,...,d} invariant only under the trivial automorphism. In this talk, we introduce a game variant of this parameter. The distinguishing game is a game with two players, the Gentle and the Rascal, with antagonist goals. This game is played on a graph G with a set of d colors (with d a positive integer). Alternatively, the two players choose a vertex of G and color it with one of the d colors. The game ends when all the vertices have been colored. Then the Gentle wins if the coloration is d-distinguishing and the Rascal wins otherwise. This game leads to a definition of two new invariants for a graph G. Those invariants are the minimum numbers of colors needed to ensure that the Gentle has a winning strategy.
We will compute those numbers for several classes of graphs, in particular, cycles, hypercubes and some cartesian products of complete graphs.
We also defined a class of graphs, the involutive graphs, for which the game distinguishing number is at most quadratic in the classical distinguishing invariant. |