Menu
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.