377 KB22 KB200820252019Balachandran, NiranjanPadinhatteeri, SajithSpiga, Pabloštevilka:1letnik:17str. 311-318ISSN:1855-3966COBISSID_HOST:18956121URN:URN:NBN:SI:doc-TNBZMBHJenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaCayley graphsCayleyjevi grafidistinguishing chromatic numberrazločevalno kromatčno številovertex transitive graphsvozliščno tranzitivni grafiVertex transitive graphs G with chisub D(G) greater then chi(G) and small automorphism group|For a graph ?$G$? and a positive integer ?$k$?, a vertex labelling ?$f: V(G) \rightarrow \{1, 2, \dots, k\}$? is said to be ?$k$?-distinguishing if no non-trivial automorphism of ?$G$? preserves the sets ?$f^{-1}(i)$? for each ?$i \in \{1, \dots, k\}$?. The distinguishing chromatic number of a graph ?$G$?, denoted ?$\chi_D(G)$?, is defined as the minimum ?$k$? such that there is a ?$k$?-distinguishing labelling of ?$V(G)$? which is also a proper coloring of the vertices of ?$G$?. In this paper, we prove the following theorem: Given ?$k \in \mathbb{N} $?, there exists an infinite sequence of vertex-transitive graphs ?$G_i = (V_i, E_i)$? such that (1.) ?$\chi_D (G_i) > \chi (G_i) > k$?, and (2.) ?$|\rm{Aut}(G_i)| < 2k|V_i|$?, where ?$\rm{Aut}(G_i)$? denotes the full automorphism group of ?$G_i$?. In particular, this answers a question posed by the first and second authors of this paperZa graf ?$G$? in pozitivno celo število ?$k$? se označitev vozlišč ?$f: V(G) \rightarrow \{1, 2, \dots, k\}$? imenuje ?$k$?-razločevalna, če noben netrivialen avtomorfizem grafa ?$G$? ne ohranja množic ?$f^{-1}(i)$? za vsak ?$i \in \{1, \dots, k\}$?. Razločevalno kromatično število grafa ?$G$?, označeno z ?$\chi_D(G)$?, je definirano kot najmanjše število ?$k$?, pri katerem obstaja ?$k$?-razločevalna označitev ?$V(G)$?, ki je tudi pravilno barvanje vozlišč grafa ?$G$?. V članku dokažemo naslednji izrek: Pri danem ?$k \in \mathbb{N}$? obstaja neskončno zaporedje vozliščno tranzitivnih grafov ?$G_i = (V_i, E_i)$?, za katere je (1.) ?$\chi_D (G_i) > \chi (G_i) > k$? in (2.) ?$|\rm{Aut}(G_i)| < 2k|V_i|$?, kjer ?$\rm{Aut}(G_i)$? označuje polno grupo avtomorfizmov grafa ?$G_i$?. To tudi odgovori na vprašanje, ki sta ga zastavila prvi in drugi avtor tega člankaTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije