Let $G$ be a graph in which each vertex initially has weight 1. In each step, the unit 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 unit acquisition number of $G$, denoted by $a_u(G)$, is the minimum cardinality of the set of vertices with positive weight at the end of the process (over all acquisition protocols). In this paper, we investigate the Erdős-Rényi random graph process $(\mathcal{G}(n,m))_{m =0}^{N}$, where $N = {n \choose 2}$. We show that asymptotically almost surely $a_u(\mathcal{G}(n,m)) = 1$ right at the time step the random graph process creates a connected graph. Since trivially $a_u(\mathcal{G}(n,m)) \ge 2$ if the graphs is disconnected, the result holds in the strongest possible sense.
@article{10_37236_9671,
author = {Konstantinos Georgiou and Somnath Kundu and Pawe{\l} Pra{\l}at},
title = {The unit acquisition number of binomial random graphs},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {3},
doi = {10.37236/9671},
zbl = {1470.05145},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9671/}
}
TY - JOUR
AU - Konstantinos Georgiou
AU - Somnath Kundu
AU - Paweł Prałat
TI - The unit acquisition number of binomial random graphs
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/9671/
DO - 10.37236/9671
ID - 10_37236_9671
ER -
%0 Journal Article
%A Konstantinos Georgiou
%A Somnath Kundu
%A Paweł Prałat
%T The unit acquisition number of binomial random graphs
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/9671/
%R 10.37236/9671
%F 10_37236_9671
Konstantinos Georgiou; Somnath Kundu; Paweł Prałat. The unit acquisition number of binomial random graphs. The electronic journal of combinatorics, Tome 28 (2021) no. 3. doi: 10.37236/9671
