TY - JOUR

T1 - The total acquisition number of random graphs

AU - Bal, Deepak

AU - Bennett, Patrick

AU - Dudek, Andrzej

AU - Prałat, Paweł

N1 - Publisher Copyright:
© 2016, Australian National University. All Rights Reserved.

PY - 2016/6/24

Y1 - 2016/6/24

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84976334745&partnerID=8YFLogxK

U2 - 10.37236/5327

DO - 10.37236/5327

M3 - Article

AN - SCOPUS:84976334745

SN - 1077-8926

VL - 23

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 2

ER -