The total acquisition number of random graphs

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

The total acquisition number of random graphs

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

Mathematics

Montclair State University

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

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₂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 - Jun 24 2016

ASJC Scopus subject areas

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

Cite this

@article{bd8431fa60fd47d9bbe9d07fbc39273e,

title = "The total acquisition number of random graphs",

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 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.",

author = "Deepak Bal and Patrick Bennett and Andrzej Dudek and Pawe{\l} Pra{\l}at",

year = "2016",

month = jun,

day = "24",

language = "English",

volume = "23",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "2",

}

TY - JOUR

T1 - The total acquisition number of random graphs

AU - Bal, Deepak

AU - Bennett, Patrick

AU - Dudek, Andrzej

AU - Prałat, Paweł

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

M3 - Article

SN - 1077-8926

VL - 23

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 2

ER -

The total acquisition number of random graphs

Abstract

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this