262 KB19 KB139 KB3 KB200820252023Sopena, ÉricWoźniak, Mariuszštevilka:1letnik:23P1.07 (7 str.)DOI:10.26493/1855-3974.2144.9e3COBISSID_HOST:149266179ISSN:1855-3966URN:URN:NBN:SI:doc-DQ0OK6VXenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaarc-colouringbarvanje lokovbarvanje lokov, ki razlikuje sosededigrafdigraphneighbour-distinguishing arc-colouringA note on the neighbour-distinguishing index of digraphs|In this note, we introduce and study a new version of neighbour-distinguishing arc-colourings of digraphs. An arc-colouring ?$\gamma$? of a digraph ?$D$? is proper if no two arcs with the same head or with the same tail are assigned the same colour. For each vertex ?$u$? of ?$D$?, we denote by ?$S_{\gamma}^- (u)$? and ?$S_{\gamma}^+ (u)$? the sets of colours that appear on the incoming arcs and on the outgoing arcs of ?$u$?, respectively. An arc colouring ?$\gamma$? of ?$D$? is neighbour-distinguishing if, for every two adjacent vertices ?$u$? and ?$v$? of ?$D$?, the ordered pairs ?$(S_{\gamma}^- (u), S_{\gamma}^+(u))$? and ?$(S_{\gamma}^- (v), S_{\gamma}^+ (v))$? are distinct. The neighbour-distinguishing index of ?$D$? is then the smallest number of colours needed for a neighbour-distinguishing arc-colouring of ?$D$?. We prove upper bounds on the neighbour-distinguishing index of various classes of digraphsV članku vpeljemo in preučujemo novo različico barvanja lokov v digrafih, ki razlikuje sosede. Barvanje lokov ?$\gamma$? digrafa ?$D$? je pravilno, če nobenima dvema lokoma z istim koncem ali z istim začetkom ni dodeljena ista barva. Za vsako vozlišče ?$u$? digrafa ?$D$? označimo z ?$S_{\gamma}^- (u)$? in ?$S_{\gamma}^+ (u)$? množici barv, ki nastopata na vhodnih lokih in na izhodnih lokih vozlišča ?$u$?. Barvanje lokov ?$\gamma$? digrafa ?$D$? razlikuje sosede, če sta za vsaka dva sosedna vozlišča ?$u$? in ?$v$? digrafa ?$D$?, urejena para ?$(S_{\gamma}^- (u), S_{\gamma}^ + (u))$? in ?$(S_{\gamma}^- (v), S_{\gamma}^+ (v))$? različna. Indeks razlikovanja sosedov digrafa ?$D$? je potem najmanjše število barv, ki so potrebne za barvanje lokov, ki razlikuje sosede v digrafu ?$D$?. Dokažemo zgornje meje za indeks razlikovanja sosedov različnih razredov digrafovTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije