The distinguishing index of the Cartesian product of finite graphs

Aleksandra Gorzkowska, Rafał Kalinowski, Monika Pilśniak


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.


Edge colouring, symmetry breaking, distinguishing index, Cartesian product of graphs

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications