V č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 digrafov.

Pravice

URN

URN:NBN:SI:DOC-DQ0OK6VX

COBISSID

149266179

DOI

10.26493/1855-3974.2144.9e3

Objavljeno

02.10.2023

Metapodatki

Citiranje

APA:

Sopena, Éric, Woźniak, Mariusz (2023). A note on the neighbour-distinguishing index of digraphs. Ars mathematica contemporanea, letnik 23, številka 1, P1.07 (7 str.). URN:NBN:SI:DOC-DQ0OK6VX from http://www.dlib.si

MLA:

Sopena, Éric, Woźniak, Mariusz. "A note on the neighbour-distinguishing index of digraphs." Ars mathematica contemporanea letnik 23. številka 1 (2023) P1.07 (7 str.).
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-DQ0OK6VX>

Ars mathematica contemporanea
2008-
(Zbirni zapis)