20.500.12556/DKUM-51858 The distinguishing chromatic number of Cartesian products of two complete graphs Razlikovalno kromatično število kartezičnega produkta dveh polnih grafov Označitev grafa ▫$G$▫ je razlikovalna, če jo ohranja le trivialni avtomorfizem grafa ▫$G$▫. Razlikovalno kromatično število grafa ▫$G$▫ je najmanjše naravno število, za katero obstaja razlikovalna označitev grafa, ki je hkrati tudi dobro barvanje. Za vse ▫$k$▫ in ▫$n$▫ je določeno razlikovalno kromatično število kartezičnih produktov ▫$K_kBox K_n$▫. V večini primerov je enako kromatičnemu številu, kar med drugim odgovori na vprašanje Choia, Hartkeja and Kaula, ali obstajajo še kakšni drugi grafi, za katere velja enakost. A labeling of a graph ▫$G$▫ is distinguishing if it is only preserved by the trivial automorphism of ▫$G$▫. The distinguishing chromatic number of ▫$G$▫ is the smallest integer ▫$k$▫ such that ▫$G$▫ has a distinguishing labeling that is at the same time a proper vertex coloring. The distinguishing chromatic number of the Cartesian product $K_kBox K_n$ is determined for all ▫$k$▫ and ▫$n$▫. In most of the cases it is equal to the chromatic number, thus answering a question of Choi, Hartke and Kaul whether there are some other graphs for which this equality holds. teorija grafov razlikovalno kromatično število grafovski avtomorfizem kartezični produkt grafov graph theory distinguishing chromatic number graph automorphism Cartesian product of graphs true true true Angleški jezik Slovenski jezik Članek v reviji 2015-07-10 15:16:09 2015-07-10 15:16:09 2024-09-25 13:43:58 2019-07-11 07:30:19 2010 0 0 Str. 1715-1720 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 15551833 15552601 0012-365X URN:SI:UM:DK:BQHDVVNR http://dx.doi.org/10.1016/j.disc.2009.11.021 1 https://dk.um.si/Dokument.php?lang=slv&id=76418 Fakulteta za naravoslovje in matematiko 0 0 0