Back to search

East Tennessee State University

Differentials of Graphs.

Abstract

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.

Degree

thesis:*
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 and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Lewis, Jason Robert

Subjects

dc:subject × 4

Rights

dc:rights
Statement dc:rights
  • Copyright by the authors.

Identifiers

dc:identifier.*
Repository record dc:identifier
https://dc.etsu.edu/etd/869

Chain of custody

source
Harvested from
East Tennessee State University
Base URL
dc.etsu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Lewis, Jason Robert. Differentials of Graphs.. Thesis - unrestricted thesis, 2004. https://dc.etsu.edu/etd/869