Proper connection and proper-walk connection of digraphs

Abstract

An arc-colored digraph D is properly (properly-walk) connected if, for any ordered pair of vertices $(u,v)$, the digraph $D$ contains a directed path (a directed walk) from $u$ to $v$ such that arcs adjacent on that path (on that walk) have distinct colors. The proper connection number $\overrightarrow{pc}(D)$ (the proper-walk connection number $\overrightarrow{wc}(D)$) of a digraph $D$ is the minimum number of colours to make $D$ properly connected (properly-walk connected). We prove that $\overrightarrow{pc}(C_n(S))\le 2$ for every circulant digraph $C_n(S)$ with $S\subseteq \{1,\dots ,n-1\},|S|\ge 2$ and $1\in S$. Furthermore, we give some sufficient conditions for a Hamiltonian digraph $D$ to satisfy $\overrightarrow{pc}(D)=\overrightarrow{wc}(D)=2$.