Spelling suggestions: "subject:"profit margin off a graph"" "subject:"profit margin oof a graph""
1 |
Differentials in GraphsMashburn, J., Haynes, T. W., Hedetniemi, S. M., Hedetniemi, S. T., Slater, P. J. 01 March 2006 (has links)
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.
|
2 |
Differentials of Graphs.Lewis, Jason Robert 01 May 2004 (has links) (PDF)
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.
|
Page generated in 0.0884 seconds