Virginia Commonwealth University
A Horizontal Edges Bound for the Independence Number of a Graph
Abstract
dc:description.abstractThe 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.
Degree
thesis:*- Name thesis:degree_name
- Master of Science
- Level thesis:degree_level
- Thesis
- Discipline thesis:degree_discipline
- Mathematical Sciences
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Grigsby, Michelle
- Contributors dc:contributor
-
- Craig Larson
Subjects
dc:subject × 3Rights
dc:rights- Statement dc:rights
-
- © The Author
Identifiers
dc:identifier.*- Identifier
- https://scholarscompass.vcu.edu/etd/2675