## Theses and Dissertations

2011

Thesis

#### Degree Name

Master of Science

#### Department

Mathematical Sciences

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.

#### Is Part Of

VCU University Archives

#### Is Part Of

VCU Theses and Dissertations

April 2011

COinS