Degree Name
MS (Master of Science)
Program
Mathematical Sciences
Date of Award
5-2004
Committee Chair or Co-Chairs
Teresa W. Haynes
Committee Members
Debra J. Knisley, George D. Poole
Abstract
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.
Document Type
Thesis - unrestricted
Recommended Citation
Lewis, Jason Robert, "Differentials of Graphs." (2004). Electronic Theses and Dissertations. Paper 869. https://dc.etsu.edu/etd/869
Copyright
Copyright by the authors.