A symmetric digraph $\overleftrightarrow{ G}$ is obtained from a simple graph $G$ by replacing each edge $uv$ with a pair of opposite arcs $\vec{ uv}$, $\overrightarrow{ vu}$. An arc-colouring $c$ of a digraph $\overleftrightarrow{ G}$ is distinguishing if the only automorphism of $\overleftrightarrow{ G}$ preserving the colouring $c$ is the identity. Behzad introduced the proper arc-colouring of type I as an arc-colouring such that any two consecutive arcs $\overrightarrow{ uv}$, $\overrightarrow{ vw}$ have distinct colours. We establish an optimal upper bound $\lceil 2\sqrt{ \Delta(G)}\rceil$ for the least number of colours in a distinguishing proper colouring of type I of a connected symmetric digraph $\overleftrightarrow{ G}$. Furthermore, we prove that the same upper bound $\lceil 2\sqrt{ \Delta(G)}\rceil$ is optimal for another type of proper colouring of $\overleftrightarrow{ G}$, when only monochromatic 2-paths are forbidden.
Categories: math.CO