The distinguishing index of the Cartesian product of finite graphs
Aleksandra Gorzkowska, Rafał Kalinowski, Monika Pilśniak · Ars Mathematica Contemporanea · 2016
The distinguishing index Dʹ(G) of a graph G is the least natural number d such that G has an edge colouring with d colours that is only preserved by the identity automorphism. In this paper we investigate the distinguishing index of the Cartesian product of connected finite graphs. We prove that for every k ≥ 2, the k-th Cartesian power of a connected graph G has distinguishing index equal 2, with the only exception Dʹ(K22) = 3. We also prove that if G and H are connected graphs that satisfy the relation 2 ≤ ∣G∣ ≤ ∣H∣ ≤ 2^∣G∣(2^∣∣G∣∣ − 1) − ∣G∣ + 2, then Dʹ(G□ H) ≤ 2 unless G□ H = K22.