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.
| Identifer | oai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-19434 |
| Date | 01 March 2006 |
| Creators | Mashburn, J., Haynes, T. W., Hedetniemi, S. M., Hedetniemi, S. T., Slater, P. J. |
| Publisher | Digital Commons @ East Tennessee State University |
| Source Sets | East Tennessee State University |
| Detected Language | English |
| Type | text |
| Source | ETSU Faculty Works |
Page generated in 0.0023 seconds