A New Game Invariant of Graphs: the Game Distinguishing Number

The distinguishing number of a graph $G$ is a symmetry related graphinvariant whose study started two decades ago. The distinguishing number $D(G)$is the least integer $d$ such that $G$ has a $d$-distinguishing coloring. Adistinguishing $d$-coloring is a coloring $c:V(G)\rightarrow\{1,...,d\}$invariant only under the trivial automorphism. In this paper, we introduce agame variant of the distinguishing number. The distinguishing game is a gamewith two players, the Gentle and the Rascal, with antagonist goals. This gameis played on a graph $G$ with a set of $d\in\mathbb N^*$ colors. Alternately,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 ifthe coloring is distinguishing and the Rascal wins otherwise. This game leadsto define two new invariants for a graph $G$, which are the minimum numbers ofcolors needed to ensure that the Gentle has a winning strategy, depending onwho starts. These invariants could be infinite, thus we start by givingsufficient conditions to have infinite game distinguishing numbers. We alsoshow that for graphs with cyclic automorphisms group of prime odd order, bothgame invariants are finite. After that, we define a class of graphs, theinvolutive graphs, for which the game distinguishing number can bequadratically bounded above by the classical distinguishing number. Thedefinition of this class is closely related to imprimitive actions whose blockshave size $2$. Then, we apply results on involutive graphs to compute the exactvalue of these invariants for hypercubes and even cycles. Finally, we study oddcycles, for which we are able to compute the exact value when their order isnot prime. In the prime order case, we give an upper bound of $3$