Conflict-free connection number of random graphs
Conflict-free connection number of random graphs
复制标题
随机图无冲突连接数
DOI：
10.1016/j.dam.2020.01.034
复制
发表时间：
2020
影响因子：
1.1
通讯作者：
Li Xueliang
中科院分区：
文献类型：
--
作者：
Gu Ran;Li Xueliang
如果任意两个顶点通过一条路径连接，而这条路径恰好包含了它的一条边所使用的颜色，那么一个边缘彩色图G就是无冲突连通的。连通图G的无冲突连接数，用c f c (G)表示，是使G无冲突连接所需的最小颜色数。在本文中，我们证明了几乎所有的图都具有无冲突连接数2。更准确地说，设G （n, p）表示Erdős-Rényi随机图模型，其中n 2对顶点中的每对都以p独立于其他对的概率作为一条边出现。证明了对于足够大的n，当p≥log n+ α (n) n时，c f c (G (n, p))≤2，其中α (n)→∞。这意味着一旦G （n, p）成为高概率连接，c f c (G (n, p))≤2。
An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path which contains a color used on exactly one of its edges. The conflict-free connection number of a connected graph G, denoted by c f c (G), is the smallest number of colors needed in order to make G conflict-free connected. In this paper, we show that almost all graphs have the conflict-free connection number 2. More precisely, let G (n, p) denote the Erdős–Rényi random graph model, in which each of the n 2 pairs of vertices appears as an edge with probability p independent from other pairs. We prove that for sufficiently large n, c f c (G (n, p))≤ 2 if p≥ log n+ α (n) n, where α (n)→∞. This means that as soon as G (n, p) becomes connected with high probability, c f c (G (n, p))≤ 2.