The distinguishing number of Cartesian products of complete graphsImrich, Wilfried (Avtor) Jerebic, Janja (Avtor) Klavžar, Sandi (Avtor) matematikateorija grafovrazlikovalno številopolni grafikartezični produkt grafovmathematicsgraph theorydistingushing numbercomplete graphsCartesian productRazlikovalno število ▫$D(G)$▫ grafa ▫$G$▫ je najmanjše število ▫$d$▫, tako da ▫$G$▫ premore označitev z ▫$d$▫ oznakami, ki jo ohranja le trivialni avtomorfizem. Dokažemo, da lahko kartezične produkte relativno tujih grafov, katerih velikosti se ne razlikujejo preveč, razlikujemo z majhnim številom barv. Za vse ▫$k$▫ in ▫$n$▫ določimo razlikovalno število kartezičnega produkta ▫$K_k square K_k$▫ in sicer bodisi eksplicitno, bodisi s kratko rekurzijo. Vpeljemo tudi stolpčno-invariantne množice vektorjev in dokažemo preklopno lemo, ki igra ključno vlogo v dokazih.20082015-07-10 15:01:43Članek v reviji51670UDK: 519.17OceCobissID: 14626649COBISS_ID: 14626905ISSN pri članku: 0195-6698NUK URN: URN:SI:UM:DK:HHXKS69Usl