The unit acquisition number of binomial random graphs (Q2048570): Difference between revisions

Summary: 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 = \binom{n}{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)) \geqslant 2\) if the graphs are disconnected, the result holds in the strongest possible sense.