#### Title

#### 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 - Open Access

#### Recommended Citation

Lewis, Jason Robert, "Differentials of Graphs." (2004). *Electronic Theses and Dissertations.* Paper 869. http://dc.etsu.edu/etd/869

#### Copyright

Copyright by the authors.