THE TOTAL ACQUISITION NUMBER OF RANDOM GRAPHS

Abstract. Let G be a graph in which each vertex initially has weight 1. In each step, the weight from a vertex u can be moved to a neighbouring vertex v, provided that the weight on v is at least as large as the weight on u. The total acquisition number of G, denoted by at(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 at(G(n, p)) = 1 with high probability, where G(n, p) is a binomial random graph. We show that p = log2 nn ≈ 1.4427 lognn is a sharp threshold for this property. We also show that almost all trees T satisfy at(T) = Θ(n), confirming another conjecture of West. 1