Differentials of Graphs.

<p>Let <em>G</em>=(<em>V</em>,<em>E</em>) 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 <em>k</em> tokens. You then place the tokens on some subset of <em>k</em> vertices of <em>V</em>. For each vertex of <em>G</em> 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(<em>X</em>) be the set of vertices in <em>V</em>-<em>X</em> that have a neighbor in a set <em>X</em>. From this game, we define the <em>differential</em> of a set <em>X</em> to be &#8706;(X) = |bd(<em>X</em>)|-|<em>X</em>|, and the <em>differential of a graph</em> to be equal to max{&#8706;(<em>X</em>)} for any subset <em>X</em> of <em>V</em>. In this paper, we introduce several different variations of the differential of a graph and study bounds on and properties of these novel parameters.</p>

Name thesis:degree_name

MS (Master of Science)

Level thesis:degree_level

Thesis - unrestricted

Discipline thesis:degree_discipline

Mathematical Sciences

Year dc:date.issued

2004

Author dc:creator

• Lewis, Jason Robert

• differential
• domination
• profit margin of a graph
• Physical Sciences and Mathematics

Statement dc:rights

• Copyright by the authors.

Repository record dc:identifier

https://dc.etsu.edu/etd/869

OAI identifier oai:identifier

oai:dc.etsu.edu:etd-2026