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(\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.
@article{10_37236_5327,
author = {Deepak Bal and Patrick Bennett and Andrzej Dudek and Pawe{\l} Pra{\l}at},
title = {The total acquisition number of random graphs},
journal = {The electronic journal of combinatorics},
year = {2016},
volume = {23},
number = {2},
doi = {10.37236/5327},
zbl = {1339.05366},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5327/}
}
TY - JOUR
AU - Deepak Bal
AU - Patrick Bennett
AU - Andrzej Dudek
AU - Paweł Prałat
TI - The total acquisition number of random graphs
JO - The electronic journal of combinatorics
PY - 2016
VL - 23
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/5327/
DO - 10.37236/5327
ID - 10_37236_5327
ER -
%0 Journal Article
%A Deepak Bal
%A Patrick Bennett
%A Andrzej Dudek
%A Paweł Prałat
%T The total acquisition number of random graphs
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/5327/
%R 10.37236/5327
%F 10_37236_5327
Deepak Bal; Patrick Bennett; Andrzej Dudek; Paweł Prałat. The total acquisition number of random graphs. The electronic journal of combinatorics, Tome 23 (2016) no. 2. doi: 10.37236/5327
