Distant sum distinguishing index of graphs with bounded minimum degree

angleški

2019

letnik 17, številka 1

razlikovalni indeks oddaljenih množic   razlikovalni indeks oddaljenih vsot   razlikovalni indeks sosednjih vsot   sosedni krepki kromatični indeks

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

Za poljuben graf ?$G=(V,E)$? z maksimalno stopnjo ?$\Delta$? in brez izoliranih povezav ter za poljubno pozitivno celo število ?$r$? označimo s ?$\chi'_{\Sigma,r}(G)$? razlikovalni indeks ?$r$?-oddaljenih vsot grafa ?$G$?. To je najmanjše celo število ?$k$?, za katerega obstaja takšno pravilno barvanje povezav ?$c:E\to\{1,2,\ldots,k\}$?, da velja ?$\sum_{e\ni u}c(e)\neq \sum_{e\ni v}c(e)$? za vsak par različnih vozlišč ?$u,v$? na razdalji največ ?$r$? v ?$G$?. Postavljena je bila domneva, da velja ?$\chi'_{\Sigma,r}(G)\leq (1+o(1))\Delta^{r-1}$? za vsak ?$r\geq 3$?. Doslej je bilo dokazano, da velja ?$\chi'_{\Sigma,r}(G)\leq 6\Delta^{r-1}$?, če je ?$r\geq 4$?. S povezovanjem verjetnostnega in konstruktivnega pristopa pokažemo, da lahko to izboljšamo na ?$\chi'_{\Sigma,r}(G)\leq (4+o(1))\Delta^{r-1}$?, če je minimalna stopnja grafa ?$G$? enaka najmanj ?$\ln^8\Delta$?.

29.05.2020