Back to search

Virginia Commonwealth University

A Horizontal Edges Bound for the Independence Number of a Graph

Abstract

dc:description.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.

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 × 3

Rights

dc:rights
Statement dc:rights
  • © The Author

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Virginia Commonwealth University
Base URL
scholarscompass.vcu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Grigsby, Michelle. A Horizontal Edges Bound for the Independence Number of a Graph. Thesis thesis, https://doi.org/10.25772/AARA-SN04