Vertex transitive graphs G with chisub D(G) greater then chi(G) and small automorphism group

angleški

2019

letnik 17, številka 1

Cayleyjevi grafi   razločevalno kromatčno število   vozliščno tranzitivni grafi

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Za 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 članka.

29.05.2020