Acquisition Parameters in Graphs
by
Paul Wenger
University of Illinois Urbana-Champaign
Coauthors: Noah Prince

Let G be a graph with weight one on each vertex. If a vertex u has a neighbor v whose weight is at least the weight on u, an acquisition move moves all of the weight on u to v. The acquisition number of G, written a(G), is the minimum number of vertices with positive weight after a sequences of acquisition moves in G. Acquisition number was introduced by Lampert and Slater in 1995.

In this talk we introduce two generalizations of acquisition on graphs. A partial acquisition move transfers an integer amount of weight from u to v and a continuous acquisition move transfers any positive amount of weight from u to v. The partial acquisition number a_p(G) and the continuous acquisition number a_c(G) are the minimum number of vertices with positive weight after a sequence of partial, respectively continuous, acquisition moves. We explore these three parameters, proving that they are all equal on paths and cycles while differing greatly on other families of graphs.

Date received: March 30, 2009