#### DOI

https://doi.org/10.25772/0WGJ-TC54

#### Defense Date

2011

#### Document Type

Thesis

#### Degree Name

Master of Science

#### Department

Mathematical Sciences

#### First Advisor

Craig Larson

#### Abstract

For a graph $G$, let $\alpha (G)$ be the cardinality of a maximum independent set, let $\mu (G)$ be the cardinality of a maximum matching and let $\xi (G)$ be the number of vertices belonging to all maximum independent sets. Boros, Golumbic and Levit showed that in connected graphs where the independence number $\alpha (G)$ is greater than the matching number $\mu (G)$, $\xi (G) \geq 1 + \alpha(G) - \mu (G)$. For any graph $G$, we will show there is a distinguished induced subgraph $G[X]$ such that, under weaker assumptions, $\xi (G) \geq 1 + \alpha (G[X]) - \mu (G[X])$. Furthermore $1 + \alpha (G[X]) - \mu (G[X]) \geq 1 + \alpha (G) - \mu (G)$ and the difference between these bounds can be arbitrarily large. Lastly some results toward a characterization of graphs with equal independence and matching numbers is given.

#### Rights

© The Author

#### Is Part Of

VCU University Archives

#### Is Part Of

VCU Theses and Dissertations

#### Date of Submission

April 2011