A note on the neighbour-distinguishing index of digraphs

Abstract

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 \emph{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.