Total Acquisition in Graphs

Abstract

Let $G$ be a weighted graph in which each vertex initially has weight $1$. A total acquisition move transfers all the weight from a vertex $u$ to a neighboring vertex $v$, under the condition that before the move the weight on $v$ is at least as large as the weight on $u$. The (total) acquisition number of $G$, written $a_{t}(G)$, is the minimum size of the set of vertices with positive weight after a sequence of total acquisition moves. Among connected $n$-vertex graphs, $a_{t}(G)$ is maximized by trees. The maximum is $\Theta(\sqrt{n\lg n})$ for trees with diameter $4$ or $5$. It is $\left\lfloor{(n+1)/3}\right\rfloor$ for trees with diameter between $6$ and $\frac23(n+1)$, and it is $\left\lceil{(2n-1-D)/4}\right\rceil$ for trees with diameter $D$ when $\frac{2}{3}(n+1)\le D\le n-1$. We characterize trees with acquisition number 1, which permits testing $a_{t}(G)\le k$ in time $O(n^{k+2})$ on trees. If $G\ne C_5$, then $\min\{a_{t}(G),a_{t}(\overline{G})\}=1$. If $G$ has diameter $2$, then $a_{t}(G)\le 32\ln n\ln\ln n$; we conjecture a constant upper bound. Indeed, $a_{t}(G)=1$ when $G$ has diameter $2$ and no $4$-cycle, except for four graphs with acquisition number $2$. Deleting one edge of an $n$-vertex graph cannot increase $a_{t}$ by more than $6.84\sqrt n$, but we construct an $n$-vertex tree with an edge whose deletion increases it by more than $\frac12\sqrt{n}$. We also obtain multiplicative upper bounds under products.