The total acquisition number of random graphs

Let G be a graph in which each vertex initially has weight 1. In each step, the 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 total acquisition number of G, denoted by a_t(G), is the minimum possible size of the set of vertices with positive weight at the end of the process. LeSaulnier, Prince, Wenger, West, and Worah asked for the minimum value of p = p(n) such that a_t(G(n, p)) = 1 with high probability, where G(n, p) is a binomial random graph. We show that p = log₂n/n≈ 1:4427 log n/n is a sharp threshold for this property. We also show that almost all trees Tsatisfy a_t(T) = Θ (n), confirming a conjecture of West.