THE TOTAL ACQUISITION NUMBER OF RANDOM GEOMETRIC GRAPHS

Description

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 cardinality of the set of vertices with positive weight at the end of the process. In this paper, we investigate random geometric graphs G(n, r) with n vertices distributed u.a.r. in [0, sqrt(n)]^2 and two vertices being adjacent if and only if their distance is at most r. We show that asymptotically almost surely a_t (G(n, r)) = Θ(n/(r lg r)^2) for the whole range of r = r_n ≥ 1 such that r lg r ≤ sqrt(n). By monotonicity, asymptotically almost surely a_t(G(n, r)) = Θ(n) if r < 1, and a_t(G(n, r)) = Θ(1) if r lg r > sqrt(n).

Abstract

International audience

Additional details