Note on directed proper connection number of a random graph
Note on directed proper connection number of a random graph
复制标题
关于随机图有向真连接数的注解
DOI：
10.1016/j.amc.2019.05.028
复制
发表时间：
2019
影响因子：
4
通讯作者：
Li Rui
中科院分区：
文献类型：
--
作者：
Gu Ran;Deng Bo;Li Rui
对于弧着色有向图D，我们说D是恰当强连通的，如果对于任意一对有序顶点（x，y），D包含一条从x到y的有向路，使得该路中的任意相邻弧具有不同的颜色。有向图D的有向真连通数pc →（D）是使D真强连通的最小颜色数。设D（n，p）表示随机有向图模型，其中有向图的每条弧都以概率p独立于其他弧被选中。证明了若p={logn + loglogn + λ（n）}/n，则pc →（D（n，p））= 2，其中λ（n）趋于无穷大.
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 p c→(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={log n+ log log n+ λ (n)}/n, then with high probability, p c→(D (n, p))= 2, where λ (n) tends to infinite.