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 $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(\mathcal{G}(n,p))=1$ with high probability, where $\mathcal{G}(n,p)$ is a binomial random graph. We show that $p=\frac{{\log }_{2}n}{n}\approx 1.4427\frac{\log n}{n}$ is a sharp threshold for this property. We also show that almost all trees $T$ satisfy $a_t(T)=\Theta (n)$, confirming a conjecture of West.

18 pages, 1 figure