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$?.

Pravice

URN

URN:NBN:SI:DOC-IVL5ZOT2

COBISSID

18094937

Objavljeno

29.05.2020

Metapodatki

Citiranje

APA:

Gorzkowska, Aleksandra, Kalinowski, Rafał, Pilśniak, Monika (2017). The distinguishing index of the Cartesian product of finite graphs. Ars mathematica contemporanea, letnik 12, številka 1, str. 77-87. URN:NBN:SI:DOC-IVL5ZOT2 from http://www.dlib.si

MLA:

Gorzkowska, Aleksandra, Kalinowski, Rafał, Pilśniak, Monika. "The distinguishing index of the Cartesian product of finite graphs." Ars mathematica contemporanea letnik 12. številka 1 (2017) str. 77-87.
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-IVL5ZOT2>

Ars mathematica contemporanea
2008-
(Zbirni zapis)