Proper connection and proper-walk connection of digraphs

摘要

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 pc→(D) (the proper-walk connection number wc→(D)) of a digraph D is the minimum number of colours to make D properly connected (properly-walk connected). We prove that pc→(Cn(S))≤2 for every circulant digraph Cn(S) with S⊆{1,…,n−1},|S|≥2 and 1∈S. Furthermore, we give some sufficient conditions for a Hamiltonian digraph D to satisfy pc→(D)=wc→(D)=2.