2020/06/23 by Konstantinos Georgiou, Somnath Kundu, Georgiou, Konstantinos +4
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics #math.CO #math.PR
paper · pdf · doi:10.48550/arxiv.2006.13294
arxiv created 2020/06/23 · openalex publication_date 2020/06/23 · arxiv updated 2020/06/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 au(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 (G(n,m))m =0N, where N = n \choose 2. We show that asymptotically almost surely au(G(n,m)) = 1 right at the time step the random graph process creates a connected graph. Since trivially au(G(n,m)) ≥ 2 if the graphs is disconnected, the result holds in the strongest possible sense.