Differentials of Graphs.

Let G=(V,E) be an arbitrary graph, and consider the following game. You are allowed to buy as many tokens from a bank as you like, at a cost of $1 each. For example, suppose you buy k tokens. You then place the tokens on some subset of k vertices of V. For each vertex of G which has no token on it, but is adjacent to a vertex with a token on it, you receive $1 from the bank. Your objective is to maximize your profit, that is, the total value received from the bank minus the cost of the tokens bought. Let bd(X) be the set of vertices in V-X that have a neighbor in a set X. From this game, we define the differential of a set X to be ∂(X) = |bd(X)|-|X|, and the differential of a graph to be equal to max{∂(X)} for any subset X of V. In this paper, we introduce several different variations of the differential of a graph and study bounds on and properties of these novel parameters