The unit acquisition number of a graph

Abstract Let G be a graph with nonnegative integer weights. A unit acquisition move transfers one unit of weight from a vertex to a neighbor that has at least as much weight. The unit acquisition number of a graph G , denoted a u ( G ) , is the minimum size that the set of vertices with positive weight can be reduced to via successive unit acquisition moves when starting from the configuration in which every vertex has weight 1. For a graph G with n vertices and minimum degree k , we prove a u ( G ) ≤ ( n − 1 ) ∕ k , with equality for complete graphs and C 5 . Also a u ( G ) is at most the minimum size of a maximal matching in G , with equality on an infinite family of graphs. Furthermore, a u ( G ) is bounded by the maximum degree and by n − 1 when G is an n -vertex tree with diameter at most 4. We also construct arbitrarily large trees with maximum degree 5 having unit acquisition number 1, obtain a linear-time algorithm to compute the unit acquisition number of a caterpillar, and show that a u ( G ) = 1 when G has diameter 2, except that the value is 2 for C 5 and the Petersen graph.