Paper detail

Game Distinguishing Numbers of Cartesian Products of Graphs

The distinguishing number of a graph $H$ is a symmetry related graph invariant whose study started two decades ago. The distinguishing number $D(H)$ is the least integer $d$ such that $H$ has a $d$-distinguishing coloring. A $d$-distinguishing coloring is a coloring $c:V(H)\rightarrow\{1,\dots,d\}$ invariant only under the trivial automorphism. In this paper, we continue the study of a game variant of this parameter, recently introduced. The distinguishing game is a game with two players, Gentle and Rascal, with antagonist goals. This game is played on a graph $H$ with a fixed set of $d\in\mathbb N^*$ colors. Alternately, the two players choose a vertex of $H$ and color it with one of the $d$ colors. The game ends when all the vertices have been colored. Then Gentle wins if the coloring is $d$-distinguishing and Rascal wins otherwise. This game defines two new invariants, which are the minimum numbers of colors needed to ensure that Gentle has a winning strategy, depending who starts the game. The invariant could eventually be infinite. In this paper, we focus on cartesian product, a graph operation well studied in the classical case. We give sufficient conditions on the order of two connected factors $H$ and $F$ relatively prime, which ensure that one of the game distinguishing numbers of the cartesian product $H\square F$ is finite. If $H$ is a so-called involutive graph, we give an upper bound of order $D^2(H)$ for one of the game distinguishing numbers of $H\square F$. Finally, using in part the previous result, we compute the exact value of these invariants for cartesian products of relatively prime cycles. It turns out that the value is either infinite or equal to $2$, depending on the parity of the product order.