The distinguishing index of the Cartesian product of finite graphs - Gorzkowska, Aleksandra (Ars mathematica contemporanea, 2017)
Razlikovalni indeks ?$D'(G)$? grafa ?$G$? je najmanjše naravno število ?$d$?, pri katerem ima ?$G$? barvanje povezav z ?$d$? barvami, ki ga ohranja samo identični avtomorfizem. V tem članku obravnavamo razlikovalni indeks kartezičnega produkta povezanih končnih grafov. Dokažemo, da ima ?$k$?-ta kartezična potenca povezanega grafa ?$G$? razlikovalni indeks enak 2 za vsak ?$k \ge 2$?, z edino izjemo ?$D'(K_2^2) = 3$?. Dokažemo tudi, da, če sta ?$G$? in ?$H$? povezana grafa, ki zadoščata relaciji ?$2 \le |G| \le |H| \le 2^{|G|}(2^{|G|} - 1) - |G| + 2$?, potem je ?$D'(G \Box H) \le 2$? razen ?$G \Box H = K_2^2$?.
Keywords: barvanje povezav; grafi; kartezični produkt grafov; razlikovalni indeks; uničenje simetrij