DOI
https://doi.org/10.25772/AARA-SN04
Defense Date
2011
Document Type
Thesis
Degree Name
Master of Science
Department
Mathematical Sciences
First Advisor
Craig Larson
Abstract
The independence number alpha of a graph is the size of a maximum independent set of vertices. An independent set is a set of vertices where every pair of vertices in non-adjacent. This number is known to be hard to compute. The bound we worked with is defined as epsilon = max[e(v)-eh(v)] over all the vertices in the vertex set, V(G). e(v) is the number of vertices at even distance from v. eh(v) is the number of edges both of whose endpoints are at even distance from v. Epsilon can be calculated in polynomial time. Siemion Fajtlowicz proved that alpha is greater than or equal to epsilon for any graph. We worked to characterize graphs where alpha=epsilon.
Rights
© The Author
Is Part Of
VCU University Archives
Is Part Of
VCU Theses and Dissertations
Date of Submission
April 2012