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.
","abstract_html":"<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 ∂(X) = |bd(<em>X</em>)|-|<em>X</em>|, and the <em>differential of a graph</em> to be equal to max{∂(<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>","abstract_has_math":true,"creators":["Lewis, Jason Robert"],"institution":null,"degree_name":"MS (Master of Science)","degree_level":"Thesis - unrestricted","degree_discipline":"Mathematical Sciences","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2004,"date_issued":"2004-05-01T07:00:00Z","date_published":"2004-05-01T07:00:00Z","updated_at":"2026-07-24T02:19:28Z","subjects":["differential","domination","profit margin of a graph","Physical Sciences and Mathematics"],"languages":[],"rights":["Copyright by the authors."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://dc.etsu.edu/etd/869","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Lewis, Jason Robert"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2004-05-01T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematical Sciences"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis - unrestricted"]},{"key":"thesis:degree_name","label":"Degree Name","values":["MS (Master of Science)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["differential","domination","profit margin of a graph","Physical Sciences and Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["Copyright by the authors."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://dc.etsu.edu/context/etd/article/2026/viewcontent/LewisJason040604f.pdf","https://dc.etsu.edu/etd/869"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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.
"]},{"key":"dc:title","label":"Title","values":["Differentials of Graphs."]}]}],"canonical_facts":{"dc:creator":["Lewis, Jason Robert"],"dc:date.issued":["2004-05-01T07:00:00Z"],"dc:description.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.
"],"dc:identifier":["https://dc.etsu.edu/context/etd/article/2026/viewcontent/LewisJason040604f.pdf","https://dc.etsu.edu/etd/869"],"dc:rights":["Copyright by the authors."],"dc:subject":["differential","domination","profit margin of a graph","Physical Sciences and Mathematics"],"dc:title":["Differentials of Graphs."],"thesis:degree_discipline":["Mathematical Sciences"],"thesis:degree_level":["Thesis - unrestricted"],"thesis:degree_name":["MS (Master of Science)"]},"updated_at":"2026-07-24T02:19:28Z"}