The Unit Acquisition Number of Binomial Random Graphs

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 (G(n,m))^N _m=0, where N =(ⁿ ₂).We show that asymptotically almost surely a_u(G)(n,m)) = 1 right at the time step the random graph process creates a connected graph. Since trivially a_u(G)(n,m)) ≥ 2 if the graphs is disconnected, the result holds in the strongest possible sense.