Note on directed proper connection number of a random graph

摘要

For an arc-colored digraph D, we say D is properly strongly connected, if for any ordered pair of vertices (x, y), D contains a directed path from x to y such that any adjacent arcs in that path have distinct colors. The directed proper connection number pc→(D) of a digraph D, is the minimum number of colors to make D properly strongly connected. Let D(n, p) denote the random digraph model, in which every arc of a digraph is chosen with probability p independently from other arcs. We prove that if p={logn+loglogn+λ(n)}/n, then with high probability, pc→(D(n,p))=2, where λ(n) tends to infinite.