论文标题
二项式随机图的单位采集数量
The Unit Acquisition Number of Binomial Random Graphs
论文作者
论文摘要
让$ g $是每个顶点最初具有重量1的图。在每个步骤中，可以移动从顶点$ u $到附近的顶点$ v $的单位权重，只要$ v $上的重量至少与$ u $的重量一样大。 $ g $的单位采集号码（用$ a_u（g）$表示）是该过程结束时具有正权重的一组顶点的最低基数（整个采集协议）。在本文中，我们研究了erdős-rényi随机图进程$（\ MATHCAL {g}（n，m））_ {m = 0}^{n} $，其中$ n = {n \ select 2} $。我们表明，渐近上几乎肯定是$ a_u（\ mathcal {g}（n，m））= 1 $在时间步骤中，随机图进程创建了一个连接的图。由于$ A_U（\ Mathcal {g}（n，m））\ ge 2 $如果图形断开了连接，则结果在最强的可能意义上保持。
Let $G$ be a graph in which each vertex initially has weight 1. In each step, the unit weight from a vertex $u$ to a neighbouring vertex $v$ can be moved, provided that the weight on $v$ is at least as large as the weight on $u$. The unit acquisition number of $G$, denoted by $a_u(G)$, is the minimum cardinality of the set of vertices with positive weight at the end of the process (over all acquisition protocols). In this paper, we investigate the Erdős-Rényi random graph process $(\mathcal{G}(n,m))_{m =0}^{N}$, where $N = {n \choose 2}$. We show that asymptotically almost surely $a_u(\mathcal{G}(n,m)) = 1$ right at the time step the random graph process creates a connected graph. Since trivially $a_u(\mathcal{G}(n,m)) \ge 2$ if the graphs is disconnected, the result holds in the strongest possible sense.
