The Unit Acquisition Number of Binomial Random Graphs - Georgiou, Konstantinos; Kundu, Somnath; Prałat, Paweł (The Electronic Journal of Combinatorics, 2021)
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))_m =0^N, where N = n 2. 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.