367 KB37 KB200820252019Przybyło, Jakubštevilka:1letnik:17str. 37-49ISSN:1855-3966COBISSID_HOST:18911833URN:URN:NBN:SI:doc-E8D7Z5KOenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaadjacent strong chromatic indexdistant set distinguishing indexdistant sum distinguishing index of a graphneighbour sum distinguishing indexrazlikovalni indeks oddaljenih množicrazlikovalni indeks oddaljenih vsotrazlikovalni indeks sosednjih vsotsosedni krepki kromatični indeksDistant sum distinguishing index of graphs with bounded minimum degree|For any graph ?$G=(V,E)$? with maximum degree ?$\Delta$? and without isolated edges, and a positive integer ?$r$?, by ?$\chi'_{\Sigma,r}(G)$? we denote the ?$r$?-distant sum distinguishing index of ?$G$?. This is the least integer ?$k$? for which a proper edge colouring ?$c:E\to\{1,2,\ldots,k\}$? exists such that ?$\sum_{e\ni u}c(e)\neq \sum_{e\ni v}c(e)$? for every pair of distinct vertices ?$u,v$? at distance at most ?$r$? in ?$G$?. It was conjectured that ?$\chi'_{\Sigma,r}(G)\leq (1+o(1))\Delta^{r-1}$? for every ?$r\geq 3$?. Thus far it has been in particular proved that ?$\chi'_{\Sigma,r}(G)\leq 6\Delta^{r-1}$? if ?$r\geq 4$?. Combining probabilistic and constructive approach, we show that this can be improved to ?$\chi'_{\Sigma,r}(G)\leq (4+o(1))\Delta^{r-1}$? if the minimum degree of ?$G$? equals at least ?$\ln^8\Delta$?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$?TEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije