A note on the neighbour-distinguishing index of digraphs

english

2023

volume 23, issue 1

arc-colouring   digraph   neighbour-distinguishing arc-colouring

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

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 digraphs.

02.10.2023