The total acquisition number of random graphs

Deepak Bal, Patrick Bennett, Andrzej Dudek, Paweł Prałat

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


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 at(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 at(G(n, p)) = 1 with high probability, where G(n, p) is a binomial random graph. We show that p = log2n/n≈ 1:4427 log n/n is a sharp threshold for this property. We also show that almost all trees Tsatisfy at(T) = Θ (n), confirming a conjecture of West.

Original languageEnglish
JournalElectronic Journal of Combinatorics
Issue number2
StatePublished - Jun 24 2016

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'The total acquisition number of random graphs'. Together they form a unique fingerprint.

Cite this