Some Results on Acquisition Numbers

Abstract

In this paper, we shall consider acquisition sequences of a graph. The formation of each acquisition sequence is a process that creates an independent set. Each acquisition sequence is a sequence of “acquisitions” which are defined on a graph $G$ for which each vertex originally has a value of one associated with it. In an acquisition, a vertex transfers all of its value to an adjacent vertex with equal or greater value. For an acquisition sequence, one continues until no more acquisitions are possible. The parameter $a(G)$ is defined to be the minimum possible number of vertices with a nonzero value at the conclusion of such an acquisition sequence. Clearly, if $S$ is a set of vertices with nonzero values at the end of some acquisition sequence, then $S$ is independent, and we call such a set $S$ an acquisition set. We show that for a given graph $G$, “Is $a(G)=1$” is NP-complete, and describe a linear time algorithm to determine the acquisition number of a caterpillar.