The total acquisition number of random graphs (Q2629497): Difference between revisions

Summary: 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.{ }\textit{T. D. LeSaulnier} et al. [SIAM J. Discrete Math. 27, No. 4, 1800--1819 (2013; Zbl 1285.05083)] 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.