The Unit Acquisition Number of Binomial Random Graphs

<p>Let <em>G</em> be a graph in which each vertex initially has weight 1. In each step, the unit weight from a vertex <em>u </em>to a neighbouring vertex <em>v</em> can be moved, provided that the weight on <em>v</em> is at least as large as the weight on <em>u</em>. The unit acquisition number of <em>G</em>, denoted by <em>a</em>_<em>u</em><em>(G)</em>, 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 (<em>G(n,m)</em>)^<em>N</em><em> </em>_<em>m=0</em>, where N =(ⁿ ₂).We show that asymptotically almost surely <em>a</em>_<em>u</em><em>(G)(n,m))</em> = 1 right at the time step the random graph process creates a connected graph. Since trivially <em>a</em>_<em>u</em><em>(G)(n,m))</em> ≥ 2 if the graphs is disconnected, the result holds in the strongest possible sense. </p>