### Abstract

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. LeSaulnier, Prince, Wenger, West, and Worah asked for the minimum value of p = p(n) such that a_{t}(G(n, p)) = 1 with high probability, where G(n, p) is a binomial random graph. We show that p = log_{2}n/n≈ 1:4427 log n/n is a sharp threshold for this property. We also show that almost all trees Tsatisfy a_{t}(T) = Θ (n), confirming a conjecture of West.

Original language | English |
---|---|

Journal | Electronic Journal of Combinatorics |

Volume | 23 |

Issue number | 2 |

State | Published - 24 Jun 2016 |

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

## Cite this

*Electronic Journal of Combinatorics*,

*23*(2).