Total Acquisition in Graphs

Let G be a weighted graph in which each vertex initially has weight 1. A total acquisition move transfers all the weight from a vertex u to a neighboring vertex v, under the condition that before the move the weight on v is at least as large as the weight on u. The (total) acquisition number of G, written at(G), is the minimum size of the set of vertices with positive weight after a sequence of total acquisition moves. Among connected n-vertex graphs, at(G) is maximized by trees. The maximum is T(√n lg n) for trees with diameter 4 or 5. It is ⌊(n + 1)/3⌋ for trees with diameter between 6 and 2 3 (n + 1), and it is ⌊(2n - 1 - D)/4⌋ for trees with diameter D when 2 /3 (n + 1) = D = n - 1. We characterize trees with acquisition number 1, which permits testing at(G) = k in time O(nk+2) on trees. If G = C 5, then min{at(G), at(G)} = 1. If G has diameter 2, then at(G) = 32 ln n ln ln n; we conjecture a constant upper bound. Indeed, at(G) = 1 when G has diameter 2 and no 4-cycle, except for four graphs with acquisition number 2. Deleting one edge of an n-vertex graph cannot increase at by more than 6.84vn, but we construct an n-vertex tree with an edge whose deletion increases it by more than 1 2vn. We also obtain multiplicative upper bounds under products. © 2013 Society for Industrial and Applied Mathematics.