The distinguishing index of the Cartesian product of finite graphs - Gorzkowska, Aleksandra (Ars mathematica contemporanea, 2017)
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 \ge 2$?, the ?$k$?-th Cartesian power of a connected graph ?$G$? has distinguishing index equal 2, with the only exception ?$D'(K_2^2) = 3$?. We also prove that if ?$G$? and ?$H$? are connected graphs that satisfy the relation ?$2 \le |G| \le |H| \le 2^{|G|}(2^{|G|} - 1) - |G| + 2$?, then ?$D'(G \Box H) \le 2$? unless ?$G \Box H = K_2^2$?.
Keywords: barvanje povezav; grafi; kartezični produkt grafov; razlikovalni indeks; uničenje simetrij