Name
Abstract | ||
|---|---|---|
Let $G$ be a graph in which each vertex initially has weight 1. In each step, the weight from a vertex $u$ can be moved to a neighbouring vertex $v$, 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(\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. |
Year | Venue | Field |
|---|---|---|
2016 | Electronic Journal of Combinatorics | Discrete mathematics,Binary logarithm,Graph,Combinatorics,Random graph,Vertex (geometry),Approx,Binomial,Conjecture,Mathematics |
DocType | Volume | Issue |
Journal | 23 | 2 |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Deepak Bal | 1 | 35 | 7.32 |
| Patrick Bennett | 2 | 5 | 1.89 |
| Andrzej Dudek | 3 | 11 | 3.41 |
| Pawel Pralat | 4 | 234 | 48.16 |