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