The Total Acquisition Number of Random Geometric Graphs

Abstract

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 cardinality of the set of vertices with positive weight at the end of the process. In this paper, we investigate random geometric graphs $G(n,r)$ with $n$ vertices distributed u.a.r. in $[0,\sqrt{n}{]}^2$ and two vertices being adjacent if and only if their distance is at most $r$. We show that asymptotically almost surely $a_t(G(n,r))=\Theta (n/(r\lg r{)}^2)$ for the whole range of $r=r_n\ge 1$ such that $r\lg r\le \sqrt{n}$. By monotonicity, asymptotically almost surely $a_t(G(n,r))=\Theta (n)$ if $r<1$, and $a_t(G(n,r))=\Theta (1)$ if $r\lg r>\sqrt{n}$.