Game distinguishing numbers of Cartesian products

Sylvain Gravier ; Kahina Meslem ; Simon Schmidt ; Souad Slimani

Ars Mathematica Contemporanea, Tome 14 (2018) no. 1, pp. 39-54.

Résumé

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 distinguishing d-coloring. A distinguishing d-coloring is a coloring c: V(H) → {1, …, 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 antagonistic goals. This game is played on a graph H with a fixed set of d ∈ 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 d-coloring is 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 be infinite. In this paper, we focus on the 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 that are relatively prime, which ensure that one of the game distinguishing numbers of the Cartesian product H▫F is finite. If H is a so-called involutive graph, we give an upper bound of order D2(H) for one of the game distinguishing numbers of H▫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.

Détail

DOI : 10.26493/1855-3974.1015.84f

Keywords: Distinguishing number, graph automorphism, combinatorial game