Differentials in graphs

Abstract

Let G = (V, E) be an arbitrary graph, and consider the following game. You are allowed to buy as many tokens as you like, say k tokens, at a cost of $1 each. 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. Your objective is to maximize your profit, that is, the total value received minus the cost of the tokens bought. Let B(X) be the set of vertices in V - X that have a neighbor in a set X. Based on this game, we define the differential of a set X to be ∂ (X) = |B(X)| - |X|, and the differential of a graph to equal the 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.